试题历届试题小朋友排队

资源限制

时间限制：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。

思路

　　从小到大排序，只能相邻两数交换，不就是冒泡排序吗？于是果断打了个冒泡排序，可是哪能那么简单呢，70分，果然超时了。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 const ll max_n=1e5+5;
 9 
10 struct node {
11     int h, c;//身高，位置交换次数 
12 }a[max_n];
13 
14 ll ans=0;//不高兴程度 
15 
16 void mySort(int n) {
17     for(int i=1; i<n; i++) {
18         bool flag=false;
19         for(int j=0; j<n-i; j++) {
20             if(a[j].h>a[j+1].h) {
21                 swap(a[j], a[j+1]);
22                 a[j].c++;
23                 a[j+1].c++;
24                 ans+=a[j].c+a[j+1].c;
25                 flag=true;
26             }
27         }
28         if(!flag) return;
29     }
30 }
31 
32 int main() {
33     int n;
34     cin>>n;
35     for(int i=0; i<n; i++) {
36         cin>>a[i].h;
37         a[i].c=0;
38     }
39     mySort(n);
40     cout<<ans<<endl;
41     return 0;
42 }

　　后来发现原来是要求逆序数，因为一个小朋友的位置交换次数取决于他前面身高比他高的人数和他后面身高比他矮的人数.

　　求逆序数可以用树状数组或者归并排序.

①归并排序

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 using namespace std;
 5 typedef long long ll;
 6 const int max_n=1e5+5;
 7 
 8 struct node {
 9     int h;
10     ll c;//身高，位置交换次数 
11 }a[max_n], b[max_n];
12 ll ans=0;
13 
14 void mergeSort(int l, int r) {
15     if(l>=r) return;
16     int mid=l+r >> 1;
17     mergeSort(l, mid);
18     mergeSort(mid+1, r);
19     int p1=l, p2=mid+1, cnt=l;
20     while(p1<=mid && p2<=r) {
21         if(a[p1].h<=a[p2].h) {
22             a[p1].c+=p2-mid-1;//加上区间[l, r]内 a[p1] 后面比他矮的人数
23             b[cnt++]=a[p1++];
24         }
25         else {
26             a[p2].c+=mid-p1+1;//加上区间[l, r]内 a[p2] 前面比他高的人数
27             b[cnt++]=a[p2++];
28         }
29     }
30     while(p1<=mid) {
31         a[p1].c+=r-mid;//加上区间[l, r]内 a[p1] 后面比他矮的人数，这种情况说明右区间[mid+1, r]的人都比他矮，所以都加上
32         b[cnt++]=a[p1++];
33     }
34      while(p2<=r) b[cnt++]=a[p2++];
35     for(int i=l; i<=r; i++) a[i]=b[i];
36 }
37 
38 int main() {
39     int n;
40     cin>>n;
41     for(int i=0; i<n; i++) {
42         cin>>a[i].h;
43         a[i].c=0;
44     }
45     mergeSort(0, n-1);
46     for(int i=0; i<n; i++) ans+=a[i].c*(a[i].c+1)/2;
47     cout<<ans<<endl;
48     return 0;
49 }

②树状数组

后面补上

试题 历届试题 小朋友排队

试题历届试题小朋友排队