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 感谢