小朋友排队

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int f(int n){
 4     int num=0;
 5     for(int i=1;i<=n;i++){
 6         num+=i;
 7     }
 8     return num;
 9 }
10 int main()
11 {
12   int array[100000];
13   memset(array,0,sizeof(array));
14   int array1[100000];
15   memset(array1,0,sizeof(array1));
16   int n;
17   cin >> n;
18   for(int i=0;i<n;i++){
19       cin >> array[i];
20   }
21   for(int i=0;i<n;i++){
22       for(int j=0;j<n;j++){
23           if(j<i){
24               if(array[j]>array[i]){
25                   array1[i]++;
26               }
27           }
28           if(j>i){
29                   if(array[j]<array[i]){
30                   array1[i]++;
31               }
32           }
33       }
34   }
35   int all=0;
36   for(int i=0;i<n;i++){
37       all+=f(array1[i]);
38   }
39   cout << all << endl;
40     return 0;
41  } 

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define SIZE1000000+10
 4 #define N 100000+10
 5 int allHigh[SIZE];     //记录每个身高的人数  题目要求最大为1000000 这里为了防止溢出加多了10
 6 int C[SIZE];   //上面的链接讲树状数组 很清晰，c[n]=a(n-a^k+1)+.........+an （其中 k 为 n 的二进制表示中从右往左数的0 的个数）
 7 long long b[N]; //记录每个人的前逆序对 +  后逆序对
 8 int n;
 9 long long judge[N];    //可以发现不高兴程度a(n) - a(n-1) ，a(n-1) - a(n-2)，... ，a(1) - a(0)是是一个等差数列，这里把它们的结果记录在judge这个数组里
10  
11 int lowbit(int x){     //求解 a^k 
12         return x & (-x);
13 }
14 
15 void add (int i, intx) {      //当数组中的元素有变更时（这里是增加），树状数组会高效的计算
16      while(i <= SIZE){
17           C[i] += x;//更新 ，统计各个身高段的人数 
18          i += lowbit(i);
19      }
20 }
21 
22 int sum (int end){  // 求数组的和 ，这时求得是a[end]左边被加进来的孩子，已经规定左边的孩子个子都比end小 
23     int re = 0; 
24     while(end > 0) {
25         re += C[end]; 
26         end -= lowbit(end); 
27     } 
28     return re; 
29 } 
30 void fun () {  //解决问题 
31         int i;
32         for(i = 0; i < n; i ++){       //遍历所以小朋友
33                scanf("%d",&allHigh[i]);
34                add(allHigh[i] + 1, 1);               // allHigh 里 对刚获取的值小朋友的身高 的人数加一
35                b[i] = (i+1) - sum(allHigh[i]+1);     //统计该小朋友b[i]的前逆序对，因为sum(allHigh[i]+1)是求身高比i小的小孩且已经加进来的总个数， 
36         }
37         memset(C, 0, sizeof(C));       //接下来要计算各个人的后逆序对需要吧C[]清空   
38         for(i = n - 1; i >= 0; i --) { //遍历所以小朋友
39         add(allHigh[i] + 1, 1);  
40         b[i] += sum(allHigh[i]);      //统计该小朋友b[i]的前逆序对 + 后逆序对， 后加进来，且个子比i小的孩子为sum(allHigh[i]) 
41     }
42 
43     long long ans = 0
44     for(i = 0; i < n; i ++){   //累加不高兴值
45         ans += judge[b[i]];  //调用之前已经计算好的等差数列数组
46     } 
47     printf("%lld", ans); 
48 
49 }
50 
51 int main () {
52       
53       int i;
54        
55 
56         scanf("%d", &n);
57 
58         memset(allHigh, 0, sizeof(allHigh));  //初始化
59         memset(C, 0, sizeof(C));
60         memset(b, 0, sizeof(b));
61 
62         judge[0] = 0;
63         for(i = 0; i < N; i ++){       //a(n) - a(n-1) ，a(n-1) - a(n-2)，... ，a(1) - a(0)是等差数列
64               judge[i] = judge[i - 1] + i;
65         }
66 
67         fun ();
68 
69         return 0;
70 
71 }