问题来源：第五届蓝桥杯预赛 C/C++本科B组第10题
问题描述：n个小朋友，身高分别为h1,h2,...hk,...,hn，站成一排，现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。求要让所有小朋友按从低到高排好队，他们的不高兴程度之和最小是多少(如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的)。
问题分析：1.对于n个小朋友中的任何一个小朋友k，分析可以得到:
a.排在k前面比k高的小朋友都会交换到k后面去(这种小朋友个数记为high)，
b.排在k后面比k低的小朋友都会交换到k前面去(这种小朋友个数记为low)，
所以最后排好序的时候，k至少交换high+low次。
2.先假设n个小朋友身高均不相等，我们通过归并排序可以求出每个小朋友的high值，设小朋友k在第k位上，是第w低的，则low = w-1 - (k-1-high)。(w-1表示比k低的总人数，k-1-high表示排在k前面比k低的人数)
3.归并排序求小朋友k的high值，初始时high[k]=0，在对身高数组a[]中a[l]~a[mid]和a[mid+1]~a[r]合并操作的时候，若对a[l]~a[mid]中的一个数a[j],若mid+1<=k<=r && a[k]<a[j],则high[k] += mid-j+1(a[j]~a[mid]都比a[k]大且排在a[k]前边，所以累加)
4.现在处理n个小朋友中，有身高相等的情况，转化为身高全不相等即可:
a.对小朋友的身高按从小到大的顺序从1~n进行重新编号，对于身高相等的小朋友，按从左到右的顺序从1~n依次编号(这样做不会影响结果).
b.重新编号方法：先将所有小朋友的身高数组(a[])赋值到另一数组(b[])并进行排序(从小到大)，对每一个a[i]，去b[]里面二分查找其相对位置k(下标)，并令b[k]--。其中二分查找返回的是最左边的a[i]==b[k]的下标k，b[k]--的目的是保证再次查到b[k]的时候查到的是后一个(这样是不会影响b[k]前面的数的)。
例题链接：(需登录)
例题：
历届试题 小朋友排队
代码：
1 #include "stdio.h" 2 #include "string.h" 3 #include "algorithm" 4 using namespace std; 5 #define N 100005 6 7 int n; 8 int a[N],b[N]; 9 10 struct node11 {12 int i; //num[k].i存第k高的小朋友在队中的位置13 int low; //num[k].low 存第k高的小朋友后面比k低的小朋友数量14 int high; //num[k].high存第k高的小朋友前面比k高的小朋友数量15 }num[N];16 17 int erfen(int *c,int k) //返回c数组中首个和k相等的数的下标18 {19 int l=1,r=n,mid;20 while(l k)31 r=mid-1;32 else33 l=mid+1;34 }35 return l;36 }37 38 void Merge(int *a,int l,int r)39 {40 if(l==r) return ;41 int i,j,k,mid;42 mid = (l+r)/2;43 Merge(a,l,mid);44 Merge(a,mid+1,r);45 for(i=l,j=mid+1,k=0;i<=mid && j<=r; )46 {47 if(a[i]<=a[j])48 b[k++] = a[i++];49 else if(a[i]>a[j])50 b[k++] = a[j],num[a[j]].high += mid-i+1,j++;51 }52 while(i<=mid)53 b[k++] = a[i++];54 while(j<=r)55 b[k++] = a[j++];56 for(i=l,j=0; i<=r; i++)57 a[i] = b[j++];58 }59 60 int main()61 {62 int i,k,w;63 long long ans,t;64 a[0]=-1;65 while(scanf("%d",&n)!=EOF)66 {67 for(i=1; i<=n; i++)68 num[i].high = 0;69 for(i=1; i<=n; i++)70 {71 scanf("%d",&a[i]);72 b[i] = a[i];73 }74 sort(b+1,b+n+1);75 for(i=1; i<=n; i++) //对a[]重新编号76 {77 k = erfen(b,a[i]);78 a[i] = k;79 b[k]--;80 num[a[i]].i = i;81 }82 Merge(a,1,n); //归并求所有小朋友的high83 ans = 0;84 for(i=1; i<=n; i++)85 {86 k = num[i].i; //k表示第i低的小朋友在队中的位置87 w = i; //w表示是第w低的88 num[i].low = w-1 - (k-1 - num[i].high);89 t = num[i].high + num[i].low;90 ans += t*(t+1)/2;91 }92 printf("%I64d\n",ans);93 }94 return 0;95 }