题目： http://acm.hdu.edu.cn/showproblem.php?pid=1394
没看到多组输入，WA了一万次。。。。。。
其实很简单，有人暴力过得，我感觉归并排序、二叉排序树求逆序数都可以，但是我没写。
1 #include <stdio.h> 2 #include <string.h> 3 4 const int MAXN = 5010; 5 6 struct Tree_Node 7 { 8 int left, right; 9 int num; 10 } tree[MAXN<<3]; 11 12 void build(int left, int right, int step) 13 { 14 tree[step].left = left; 15 tree[step].right = right; 16 tree[step].num = 0; 17 if(left == right) 18 return; 19 int mid = (left + right) >> 1; 20 build(left, mid, step<<1); 21 build(mid+1, right, step<<1|1); 22 } 23 24 void insert(int cur, int step) 25 { 26 if(cur >= tree[step].left && cur <= tree[step].right) 27 tree[step].num++; 28 if(tree[step].left == tree[step].right) 29 return; 30 int mid = (tree[step].left + tree[step].right) >> 1; 31 if(cur <= mid) 32 insert(cur, step<<1); 33 else 34 insert(cur, step<<1|1); 35 } 36 37 int query(int left, int right, int step) 38 { 39 if(tree[step].left == left && tree[step].right == right) 40 { 41 return tree[step].num; 42 } 43 int mid = (tree[step].left + tree[step].right) >> 1; 44 if(right <= mid) 45 { 46 return query(left, right, step<<1); 47 } 48 else if(left > mid) 49 { 50 return query(left, right, step<<1|1); 51 } 52 else 53 { 54 return query(left, mid, step<<1) + query(mid+1, right, step<<1|1); 55 } 56 } 57 58 int main() 59 { 60 int n, x[MAXN]; 61 while(scanf("%d", &n) != EOF) 62 { 63 int ans = 0; 64 build(0, n, 1); 65 for(int i = 0; i < n; i++) 66 { 67 scanf("%d", &x[i]); 68 ans += query(x[i]+1, n, 1); 69 insert(x[i], 1); 70 } 71 int tmp = ans; 72 for(int i = 0; i < n; i++) 73 { 74 tmp += n - x[i] - x[i] - 1; 75 if(tmp < ans)ans = tmp; 76 } 77 printf("%d ", ans); 78 } 79 return 0; 80 }