关于本题的ans计数的疑惑?

P1908 逆序对

vegetablebird4396 @ 2020-05-29 11:17:05

#include <bits/stdc++.h>
using namespace std;
/*     本次的代码中,数组要从1开始计数,不从0开始        */
long long int a[500050],tool[500050],ans=0;

int main()
{
    void mer_sort(long long int a[],long long int lef,long long int mid,long long int rig);
    void merge_tool(long long int a[],long long int lef,long long int rig);
    long long int n;    scanf("%lld", &n);
    for(long long int i=1;i<=n;i++) scanf("%lld", &a[i]);
    merge_tool(a,1,n);
    printf("%lld",ans);
    system("pause");
}

void mer_sort(long long int a[],long long int lef,long long int mid,long long int rig)
{
    long long int i=lef,j=mid+1,k=lef;//lef , mid & rig need attention!!!
    while(i<=mid&&j<=rig)
    {
        if(a[i]<=a[j]) tool[k++]=a[i++];
        else
        {           
            tool[k++]=a[j++];           
            ans+=mid-i+1;
        }       
    }
    if(i>mid)
        for(long long int t=j;t<=rig;t++)   tool[k++]=a[t];
    if(j>rig)
        for(long long int t=i;t<=mid;t++)   tool[k++]=a[t];
    for(long long int t=lef;t<=rig;t++) a[t]=tool[t];
}

void merge_tool(long long int a[],long long int lef,long long int rig)
{
    if(lef>=rig) return;
    else
    {
        merge_tool(a,lef,(lef+rig)/2);
        merge_tool(a,(rig+lef)/2+1,rig);
        mer_sort(a,lef,(rig+lef)/2,rig);
    }
}

就是在mer_sort()函数中的27行
ans的计数代码那里
为何要使用ans+=mid-i+1;
鄙人用ans+=j-i; 就全WA了 /雾


by metaphysis @ 2020-05-29 11:23:24

mer_srot中,数组a中从lef到mid,从mid到rig都已经按升序排列,现在进行合并,如果发现a[i]>a[j],注意i是枚举左半部分的元素,j是枚举右半部分元素,表明从a[i]到a[mid]的元素与a[j]构成逆序对,逆序对数增加 mid - i + 1对。

@vegetablebird4396


by FZzzz @ 2020-05-29 11:23:34

因为你算的是左半边对右半边的贡献吧


by metaphysis @ 2020-05-29 11:24:19

您自己画画图,很容易理解。

@vegetablebird4396


by vegetablebird4396 @ 2020-05-29 11:25:16

归并排序不是要插入嘛

10 20 30 40 (隔开)15 16 17 38

(1-4有序,5-8有序)

例如: 8th数据比4th数据小,插入到新数组里,不是需要交换的次数是8-4=4(在原数组中的数据交换的次数)

mid -i +1 岂不是就是(1+8)/2-5+1=0 ?/雾 (或者这里的数组其实不是上面那种的?毕竟是递归进行排序的???)


by vegetablebird4396 @ 2020-05-29 11:27:51

@metaphysis 哦哦哦,这里是增加的逆序对的数目,而不是完成排序插入的交换次数吧?


by metaphysis @ 2020-05-29 11:31:44

嗯,是的。

@vegetablebird4396


by vegetablebird4396 @ 2020-05-29 16:33:00

@FZzzz 了解了,谢谢


by vegetablebird4396 @ 2020-05-29 16:33:10

@metaphysis 感谢


|