题目传送门
【题目大意】
给定一个长度为$n$的序列$a$，在只允许交换相邻两个数的情况下，求至少需要交换多少次才能使得$a$从小到大排序。
【思路分析】
这题的实质是冒泡排序法的过程，每交换一次就会使整个序列的逆序对减少1，最后整个序列的逆序对个数为0，即题目的答案为序列中的逆序对个数，直接用归并排序求出逆序对个数即可。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #define rg register 6 #define go(i,a,b) for(rg int i=a;i<=b;i++) 7 #define ll long long 8 using namespace std; 9 const int N=500002; 10 int n,a[N],b[N]; 11 ll px(int l,int r){ 12 if(l==r) return 0; 13 int mid=(l+r)/2;ll ans=0; 14 ans+=px(l,mid);ans+=px(mid+1,r); 15 int i=l,j=mid+1; 16 go(k,l,r) 17 if(j>r||(i<=mid&&a[i]<a[j])) b[k]=a[i++]; 18 else b[k]=a[j++],ans+=mid-i+1; 19 go(k,l,r) a[k]=b[k]; 20 return ans; 21 } 22 int main(){ 23 scanf("%d",&n); 24 while(n){ 25 go(i,1,n) scanf("%d",&a[i]); 26 printf("%lld\n",px(1,n)); 27 scanf("%d",&n); 28 } 29 return 0; 30 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11248992.html
相关资源：JAVA上百实例源码以及开源项目