Ultra-QuickSort POJ2299 求逆序对个数
程序员文章站
2022-05-10 15:12:13
...
给定长度为n(<=5e5)的序列a,如果只能交换相邻的两个数,求至少需要多少次交换才能把a从小到大排序。
题解:明显,求个逆序对就完事了,归并排序可求逆序对。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
int a[N],b[N];
ll cnt;
void merge_sort(int l,int r)
{
if(r-l>0){
int mid=(l+r)/2 ;
int i=l;
int p=l,q=mid+1;
merge_sort(l,mid);
merge_sort(mid+1,r);
while(p<=mid||q<=r){
if(q>r||(p<=mid&&a[p]<=a[q]))
b[i++]=a[p++];
else{
b[i++]=a[q++];
cnt+=mid-p+1;
}
}
for(i=l;i<=r;i++)
a[i]=b[i];
}
}
int main()
{
int n;
while((cin>>n)&&n!=0){
cnt=0;
for(int i=1;i<=n;i++)
cin>>a[i];
merge_sort(1,n);
cout<<cnt<<endl;
}
return 0;
}
上一篇: HTML常见标签学习
下一篇: html标签汇总(待补充)