小朋友排队

问题描述

　　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。

Algorithm

这个题很像是排序（插入排序），找它的逆序对，但是题目下面却有数据大小的说明，那么肯定不能用一般的思路。网上发现了许多文章都是用的树状数组，树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值。

这里我先用了归并排序，时间复杂度为nlogn，但是却只通过了30%，按理来讲可以通过至少50%，但是有的结果却错了，只有3个运行超时。所以接下来打算用树状数组做一做。

后记：从理论上来讲，归并排序不可能出问题，但是理解起来比树状数组还......

AC

归并排序法

 1 #include<iostream>
 2 #include<cstring>
 3 #include<stdio.h>
 4 
 5 using namespace std; 
 6 
 7 typedef long long ll;
 8 
 9 const ll MAXN = 100009;
10 ll ret = 0;
11 
12 // 合并 
13 ll s[MAXN];
14 ll k = 0;
15 void merge(ll *a, ll l, ll mid, ll r, ll *temp) 
16 {
17     ll i = l;        // 左序列指针 
18     ll j = mid+1;    // 右 
19     ll t = 0;        // 临时数组指针
20     while(i <= mid && j <= r){
21         if(a[i] <= a[j]){
22             temp[t++] = a[i++];
23         } 
24         else{
25             // 记录要交换的数交换的次数 
26             // 最开始差点还用了桶排序...还好我看到了100万的数据... 
27             // s[a[j]] += mid - i + 1;
28             s[j] += mid - i + 1;
29             for(ll tt = i;tt<mid+1;tt++)
30                 s[tt]++;
31                 // s[a[tt]]++;
32                 
33             temp[t++] = a[j++];
34             ret += mid - i + 1; // 逆序数对数 
35         }
36     }
37     
38     // 将左边的剩余元素填入 temp 
39     while(i <= mid) temp[t++] = a[i++];
40     // 右 
41     while(j <= r) temp[t++] = a[j++];
42     // 将 temp 中的元素拷入原始数组中 
43     t = 0;
44     while(l <= r) a[l++] = temp[t++];
45     
46     return;
47 }
48 
49 // 归并排序 
50 void merge_sort(ll *a, ll l, ll r, ll *temp)
51 {
52     if(l < r){    // 分治法 
53         ll mid = (l + r)/2;
54         merge_sort(a, l, mid, temp);
55         merge_sort(a, mid+1, r, temp);
56         merge(a, l, mid, r, temp);
57         return;
58     }
59 }
60 
61 int main()
62 {    // 1, 3, 2, 4, 5, 8, 6, 7, 9
63     ll a[MAXN];
64     ll temp[MAXN];
65     memset(a, 0, sizeof(a));
66     memset(temp, 0, sizeof(temp));
67     ll r = 0;
68     cin>>r;
69     for(ll i=0;i<r;i++)
70         scanf("%d", &a[i]);
71     merge_sort(a, 0, r-1, temp);
72     // cout<<"ret:"<<ret<<'
';
73     /*
74     for(ll i=0;i<r+1;i++)
75         cout<<a[i]<<" ";
76     cout<<'
'; 
77     
78     for(ll i=0;i<r;i++)
79         cout<<s[i]<<" ";
80     cout<<'
'; 
81     */
82     ll ans = 0;
83     for(ll i=0;i<=r;i++){
84         ans += (s[i] + 1)*s[i]/2;    
85     }
86     cout<<ans<<'
';
87     
88     return 0;
89 }

View Code

树状数组法

  1 #include<iostream>
  2 #include<cstring>
  3 #include<stdio.h>
  4 
  5 using namespace std; 
  6 
  7 typedef long long ll;
  8 
  9 // 空间要开够...... 
 10 const ll MAXN = 1e6+9;
 11 ll a[MAXN];
 12 ll c[MAXN];
 13 ll ret[MAXN];
 14 ll n;
 15 
 16 // int lowbit(int x) {return x&(x^(x–1));}
 17 
 18 // 注意 x 不能为 0, 因为 0&0 = 0
 19 int lowbit(int x) {return x&(-x);}
 20 
 21 int Sum(int n)
 22 {
 23     int s = 0;
 24     while(n > 0)
 25     {
 26         s +=  c[n];
 27         n -= lowbit(n);
 28     }
 29     return s;
 30  } 
 31  
 32 void change(int i, int x)
 33 {    // 居然是这个 MAXN 在作怪..., 算了, 先背下来 
 34     while(i <= MAXN)
 35     {    
 36         c[i] += x;
 37         i += lowbit(i);
 38     }
 39 }
 40 
 41 int find_interval(int l, int r)
 42 { 
 43     return Sum(r) - Sum(l-1);
 44 }
 45 
 46 void fun(int n)
 47 {
 48     memset(ret, 0, sizeof(ret));
 49     memset(c, 0, sizeof(c));
 50     for(int i=0;i<n;i++){
 51         scanf("%d", &a[i]);
 52         change(a[i]+1, 1);
 53         ret[i] = (i+1) - Sum(a[i]+1);
 54     }
 55     memset(c, 0, sizeof(c));
 56     for(int i=n-1;i>=0;i--){
 57         change(a[i]+1, 1);
 58         ret[i] += Sum(a[i]);
 59     }
 60     ll ans = 0;
 61     for(int i=0;i<n;i++)
 62         ans += (ret[i]+1)*ret[i]/2;
 63     cout<<ans<<'
';
 64 }
 65 
 66 int main()
 67 {
 68     while(cin>>n)
 69     { 
 70         fun(n);    
 71     }
 72     
 73     return 0;
 74 }
 75 
 76 /*------------------------------*/
 77 
 78 /*
 79 ll ans = 0;
 80         memset(a, 0, sizeof(a));
 81         memset(c, 0, sizeof(c));
 82         memset(ret, 0, sizeof(ret));
 83         for(int i=1;i<=n;i++){
 84             scanf("%I64d", &a[i]);
 85             change(a[i]+1, 1);
 86             ans += i - Sum(a[i]);
 87             ret[i] = i - Sum(a[i]);
 88         }
 89         memset(c, 0, sizeof(c));
 90         for(int i=n;i>0;i--){
 91             change(a[i], 1);
 92             ret[i] += Sum(a[i]);
 93         }
 94         cout<<"ans: "<<ans<<endl;
 95         ll cc = 0;
 96         for(int i=1;i<=n;i++)
 97             cc += (1+ret[i])*ret[i]/2;
 98         cout<<cc<<'
';
 99 */
100 
101 /*-----------------------------分割线------------------------------*/
102 /*
103 9
104 1 2 3 4 5 6 7 8 9
105 */
106 /*
107 
108 typedef long long ll;
109 
110 const ll MAXN = 100009;
111 ll ret = 0;
112 
113 // 合并 
114 ll s[MAXN];
115 ll k = 0;
116 void merge(ll *a, ll l, ll mid, ll r, ll *temp) 
117 {
118     ll i = l;        // 左序列指针 
119     ll j = mid+1;    // 右 
120     ll t = 0;        // 临时数组指针
121     while(i <= mid && j <= r){
122         if(a[i] <= a[j]){
123             temp[t++] = a[i++];
124         } 
125         else{
126             // 记录要交换的数交换的次数 
127             // 最开始差点还用了桶排序...还好我看到了100万的数据... 
128             // s[a[j]] += mid - i + 1;
129             s[j] += mid - i + 1;
130             for(ll tt = i;tt<mid+1;tt++)
131                 s[tt]++;
132                 // s[a[tt]]++;
133                 
134             temp[t++] = a[j++];
135             ret += mid - i + 1; // 逆序数对数 
136         }
137     }
138     
139     // 将左边的剩余元素填入 temp 
140     while(i <= mid) temp[t++] = a[i++];
141     // 右 
142     while(j <= r) temp[t++] = a[j++];
143     // 将 temp 中的元素拷入原始数组中 
144     t = 0;
145     while(l <= r) a[l++] = temp[t++];
146     
147     return;
148 }
149 
150 // 归并排序 
151 void merge_sort(ll *a, ll l, ll r, ll *temp)
152 {
153     if(l < r){    // 分治法 
154         ll mid = (l + r)/2;
155         merge_sort(a, l, mid, temp);
156         merge_sort(a, mid+1, r, temp);
157         merge(a, l, mid, r, temp);
158         return;
159     }
160 }
161 
162 int main()
163 {    // 1, 3, 2, 4, 5, 8, 6, 7, 9
164     ll a[MAXN];
165     ll temp[MAXN];
166     memset(a, 0, sizeof(a));
167     memset(temp, 0, sizeof(temp));
168     ll r = 0;
169     cin>>r;
170     for(ll i=0;i<r;i++)
171         scanf("%d", &a[i]);
172     merge_sort(a, 0, r-1, temp);
173     
174     ll ans = 0;
175     for(ll i=0;i<=r;i++){
176         ans += (s[i] + 1)*s[i]/2;    
177     }
178     cout<<ans<<'
';
179     
180     return 0;
181 }
182 
183 */

View Code

2019-02-22

20:58:02