题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4911
题目给出一个序列和一个操作数k，操作集合是交换任意两个相邻的数，问操作k次之后序列的最小逆序对数量。一个没有升序排列的数列一定存在两个相邻的数是逆序对，只要对这两个数进行交换就可以使逆序对的数量减少一个，否则逆序对的数量会增加。从归并排序的过程来看，归并排序将一个序列划分成两个有序的序列，在从这个两个序列之间划分成四个序列，每个序列中是有序的，只有序列之间才存在逆序对，所以容易求得整个序列的逆序对数量。用归并排序的原因是给出的数的数量级过大，否则可以用树状数组来求解。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x7ffffff 20 inline int read(){ 21 int ans=0,w=1; 22 char ch=getchar(); 23 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 25 return ans*w; 26 } 27 int n,m,t; 28 const int maxn=1e5+10; 29 int a[maxn],b[maxn]; 30 ll res=0; 31 void mergesort(int l,int r) 32 { 33 if(l==r)return; 34 int mid=l+r>>1; 35 mergesort(l,mid); 36 mergesort(mid+1,r); 37 int i=l,j=mid+1,cnt=0; 38 while(i<=mid&&j<=r) 39 { 40 if(a[i]>a[j])res+=mid-i+1,b[cnt++]=a[j++]; 41 else b[cnt++]=a[i++]; 42 } 43 while(i<=mid)b[cnt++]=a[i++]; 44 while(j<=r)b[cnt++]=a[j++]; 45 f(i,0,cnt-1)a[l+i]=b[i];//每次将指定长度的b数组复制回原数组 46 } 47 int main() 48 { 49 //freopen("input.txt","r",stdin); 50 //freopen("output.txt","w",stdout); 51 std::ios::sync_with_stdio(false); 52 while(~scanf("%d%d",&n,&m)) 53 { 54 f(i,0,n-1)a[i]=read(); 55 res=0; 56 mergesort(0,n-1); 57 if(m>=res)pf("0 "); 58 else pf("%lld ",res-m);//不能将所有相邻逆序对交换 59 } 60 }