题目：http://acm.hdu.edu.cn/showproblem.php?pid=1394
求最小的逆序数，在此贴下逆序数的概念：
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。
也是就说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。
如：0 3 4 1 2
设逆序数初始n = 0；
由于0后面没有比它小的，n = 0
3后面有1,2 n = 2
4后面有1,2,n = 2
所以该序列逆序数为 n=2+2=4
其根据题意移动产生的序列有(每次将第一个字母移到最后一个)
3 4 1 2 0 逆序数：8
4 1 2 0 3 逆序数：6
1 2 0 3 4 逆序数：2
2 0 3 4 1 逆序数：4
所以最小逆序数为2
这里有一个求最小逆序数的规律，只要知道初始序列的逆序数就能够递推比较得出最小逆序数
引用上面的例子
3 4 1 2 0 逆序数：8
4 1 2 0 3 逆序数：6
3后面比3小的数有1,2,0，所以逆序对为t=3，比3大的数只有4，所以顺序对为1，即顺序对=n-1-t,n表示序列中数字的总个数，当3移到最后一位时，逆序对转化成顺序对，
所以原来的逆序数k要减去对于该数的原来的逆序对，而顺序对转化成逆序对，所以要加上
归纳总结得到 现在的逆序数=k+(n-1-t)-t=k+n-2t-1
#include<cstdio> #include<algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn = 5555; int sum[maxn << 2]; void pushup(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void build(int l, int r, int rt) { sum[rt] = 0; if (l == r) return; int m = (l + r) >> 1; build(lson); build(rson); } void update(int p, int l, int r, int rt) { if (l == r){ sum[rt]++; return; } int m = (l + r) >> 1; if (p <= m) update(p, lson); else update(p, rson); pushup(rt); } int query(int L, int R, int l, int r, int rt) { if (L <= l&&r <= R) return sum[rt]; int ret = 0; int m = (l + r) >> 1; if (L <= m) ret += query(L, R, lson); if (R > m) ret += query(L, R, rson); return ret; } int x[maxn]; int main() { int n; while (~scanf("%d", &n)){ build(0, n - 1, 1); int sum = 0; //求出初始字符串的逆序数，这里也可以用暴力搜索出初始然后递推 for (int i = 0; i < n; i++){ scanf("%d", &x[i]); sum += query(x[i], n - 1, 0, n - 1, 1); update(x[i], 0, n - 1, 1); } int ret = sum; for (int i = 0; i < n-1; i++){//这里只要执行n-1次就行了 sum += n - 2 * x[i] - 1;//以x[i]开头的字符串，这里是从0到n-1，所以x[i]后面有x[i]个比他小的，根据递推公式即可得出 ret = min(ret, sum); } printf("%d ", ret); } return 0; }