题意：
给一个n个数的序列a1, a2, ..., an ，这些数的范围是0～n-1， 可以把前面m个数移动到后面去，形成新序列：
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
求这些序列中，逆序数最少的是多少？
树状数组：
分析：c数组里的值代表个数，下标代表等于哪个值，是按照顺序排的，所以sum(n)-sum(a[i])，就能减出来比a[i]大的数值了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <map> 7 #include <algorithm> 8 #define LL __int64 9 const int maxn = 5000+10; 10 using namespace std; 11 int c[maxn], a[maxn], n; 12 13 int lowbit(int x) 14 { 15 return x&(-x); 16 } 17 void add(int x,int d) 18 { 19 while(x <= n) 20 { 21 c[x] += d; 22 x +=lowbit(x); 23 } 24 } 25 LL sum(int x) 26 { 27 LL ret = 0; 28 while(x > 0) 29 { 30 ret += c[x]; 31 x -= lowbit(x); 32 } 33 return ret; 34 } 35 36 int main() 37 { 38 int i, ans, tmp; 39 while(~scanf("%d", &n)) 40 { 41 ans = 0; 42 memset(c, 0, sizeof(c)); //不要忘了清0 43 for(i = 1; i <= n; i++) 44 { 45 scanf("%d", &a[i]); 46 a[i] ++; //因为是从0到n-1的 47 ans += sum(n)-sum(a[i]); //貌似a[i]太大的话就不行了吧 48 add(a[i], 1); //c数组里的值代表个数，下标代表等于哪个值 49 } 50 tmp = ans; 51 for(i = 1; i <= n; i++) 52 { 53 tmp += n-a[i]-(a[i]-1); //是一个公式，我没想明白为什么 54 ans = min(ans, tmp); 55 } 56 printf("%d ", ans); 57 } 58 return 0; 59 }
归并排序的做法：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #define LL __int64 7 const int maxn = 5000+10; 8 using namespace std; 9 int n; 10 int sum, b[maxn], a[maxn], a2[maxn]; 11 12 void merge_sort(int *A, int x, int y, int *T) 13 { 14 if(y-x>1) 15 { 16 int m=x+(y-x)/2; 17 int p=x, q=m, i=x; 18 merge_sort(A,x,m,T); 19 merge_sort(A,m,y,T); 20 while(p<m || q<y) 21 { 22 if(q>=y ||(p<m && A[p] <= A[q])) 23 T[i++] = A[p++]; 24 else 25 { 26 T[i++] = A[q++]; 27 sum+=m-p; 28 } 29 30 } 31 for(i=x; i<y; i++) 32 A[i] = T[i]; 33 } 34 }; 35 36 int main() 37 { 38 int i; 39 int tmp; 40 while(~scanf("%d", &n)) 41 { 42 sum = 0; 43 memset(b, 0, sizeof(b)); 44 for(i = 0; i < n; i++) //注意这是从0开始的，因为归并排序的原因 45 { 46 scanf("%d", &a[i]); 47 a2[i] = a[i]; 48 } 49 merge_sort(a, 0, n, b); 50 tmp = sum; 51 for(i = 0; i < n; i++) 52 { 53 tmp += n-1-a2[i]-a2[i]; //一定要注意这个是a2[]; 因为之前的a[]的顺序已经改变了。还要注意这个公式 54 sum = min(sum, tmp); //和上一个树状数组的不同是上一个a[]++了。 55 } 56 printf("%d ", sum); 57 } 58 return 0; 59 }