蓝桥杯试题历届试题小朋友排队树状数组

问题描述

　　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。

解题思路:

　　若两个孩子身高为逆序对( i<j, Hi>Hj( Hi:i位置孩子身高 ) )，则需要交换位置，双方的不高兴程度均+1。若直接用冒泡排序，时间复杂度为O( n^2 )。

　　可以选取BIT(Binary Index Tree 树状数组)数据结构解决。

　　　　对于每个位置的孩子，其交换次数取决于左边身高比他高的与右边身高比他低的，两次运用BIT解决。

　　　　BIT求逆序对:构建一个值范围是 1-Max_H的BIT，按 j = 0,1,...,n顺序进行如下操作(其左边比他高的)

- 把 j - (BIT查询得到的前Hi项和)加入对应位置的不开心程度
- 把BIT中Hi位置上值+1 (注意此题身高可能为0,所以所有身高都+1处理否则会陷入死循环)

　　　　对于每个j，(BIT查询到前Hi项和)的个数是 i<j， Hi<=Hj的个数，把这个值用 j 减去之后，得到的就是 i<j ，Hi>Hj的个数。

　　对于BIT求和和更新操作只需要O( logn )，循环n次最终解题的时间复杂度为O( nlogn )。

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 typedef long long int ll;
 6 
 7 const int Max_N = 100000;
 8 const ll Max_H = 1000000;
 9 
10 //输入
11 int n;
12 int H[Max_N]; //身高 
13 
14 int count[Max_N]; //不高兴程度 
15 int bit[Max_H+1]; //BIT 1-Max_H
16 
17 int sum( int i );  //计算 1-i的和 
18 void add( int i, int x ); //更新 ai += x 
19 void solve(); 
20 
21 int main()
22 {
23     scanf("%d",&n);
24     for( int i=0; i<n; i++ ){
25         scanf("%d",&H[i]);
26         H[i]++; //防止为0 
27     }
28     
29     solve();
30     
31     return 0;
32 }
33 
34 int sum( int i )
35 {
36     int s = 0;
37     while( i>0 )
38     {
39         s += bit[i];
40         i -= i&-i;    
41     }    
42     return s;
43 } 
44 
45 void add( int i, int x )
46 {
47     while( i<=Max_H )
48     {
49         bit[i] += x;
50         i += i&-i;
51     }
52 }
53 
54 void solve()
55 {
56     //左边比其身高高的 
57     for( int j=0; j<n; j++ )
58     {
59         count[j] += j - sum( H[j] );
60         add( H[j], 1 ); 
61     }
62     
63     //右边比其升高低的 
64     memset(bit,0,sizeof(bit));
65     for( int j=n-1; j>=0; j-- )
66     {
67         count[j] += sum( H[j]-1 );
68         add( H[j], 1 );
69     }
70     
71     ll s = 0;
72     for( int i=0; i<n; i++ )
73     {
74         s += ( (ll)(count[i]+1)*count[i] / 2 );
75     }
76     printf("%lld
",s);
77 }

View Code

/*　冒泡排序的时间复杂度为O( n^2 )，同时归并等基于比较的排序时间复杂度只需要O( nlogn )，同样在比较的同时记录比较次数即可。 */

蓝桥杯 试题 历届试题 小朋友排队 树状数组

蓝桥杯试题历届试题小朋友排队树状数组