01_归并排序求逆序数(例：蓝桥杯--小朋友排队)

浏览数：36 / 时间：2015年06月08日

问题来源：第五届蓝桥杯预赛 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]前面的数的)。

例题链接：http://lx.lanqiao.org/problem.page?gpid=T123(需登录)

例题：

历届试题小朋友排队

时间限制：1.0s 内存限制：256.0MB

问题描述

　　n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
　　每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。
　　如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。
　　请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
　　如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入格式

　　输入的第一行包含一个整数n，表示小朋友的个数。
　　第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。

输出格式

　　输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

样例输入

3
3 2 1

样例输出

样例说明

　　首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。

数据规模和约定

　　对于10%的数据， 1<=n<=10；
　　对于30%的数据， 1<=n<=1000；
　　对于50%的数据， 1<=n<=10000；
　　对于100%的数据，1<=n<=100000，0<=Hi<=1000000。

代码：

 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 node
11 {
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<r)
21     {
22         mid = (l+r)/2;
23         if(c[mid]==k)
24         {
25             if(c[mid-1]<k)
26                 return mid;
27             else
28                 r=mid-1;
29         }
30         else if(c[mid]>k)
31             r=mid-1;
32         else
33             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);  //归并求所有小朋友的high
83         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 }