hdu 1394 zoj 1484 求旋轉序列的逆序數（並歸排序）

題意：給出一序列，你可以循環移動它（就是把後面的一段移動到前面），問可以移動的並產生的最小逆序數。 求逆序可以用並歸排序，復雜度為O(nlogn)，但是如果每移動一次就求一次的話肯定會超時，網上題解都說可以用並歸做，想了好久，最後發現"the next line contains a permutation of the n integers from 0 to n-1"，坑爹的家伙，這些數竟然是從0到n-1的。 這樣就可以做了，推導一下可以發現每移動一位，數列的逆序數就會又規律的變化，和它有關的且它是較大數的逆序數對會減小，其實就是序列排序完比它小的數的個數，其實就是它本身的值；而它是較小數的逆序數對就是比它大的個數。 所以只要排序一遍，求出當前逆序數，然後模擬一下循環一遍會產生的逆序數，取得最小值就行了。 代碼：

 
 /* 
 *   Author:        illuz <[email protected]> 
 *   Blog:          http://blog.csdn.net/hcbbt 
 *   File:          hdu1394.cpp 
 *   Lauguage:      C/C++ 
 *   Create Date:   2013-08-30 10:28:05 
 *   Descripton:    hdu1394, Minimum Inversion Number, partitation, simutation  
 */  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
#define rep(i, n) for (int i = 0; i < (n); i++)  
#define repu(i, a, b) for (int i = (a); i < (b); i++)  
  
const int MAXN = 5100;  
int n, a[MAXN], b[MAXN], t[MAXN];  
int cnt, Min, sum;  
  
void mergeSort(int* A, int x, int y) {  
    if (y - x <= 1) return;  
    int m = x + (y - x) / 2;  
    mergeSort(A, x, m);  
    mergeSort(A, m, y);  
    int p = x, q = m, i = x;  
    while (p < m || q < y)  
        if (q >= y || (p < m && A[p] <= A[q]))  
            t[i++] = A[p++];  
        else  
            t[i++] = A[q++], cnt += m - p;  
    repu(i, x, y) A[i] = t[i];  
}  
  
int main() {  
    while (scanf("%d", &n) != EOF) {  
        rep(i, n)  
            scanf("%d", &a[i]);  
        int Min = 0xffffff;  
        memcpy(b, a, sizeof(a));  
        cnt = 0;  
        mergeSort(a, 0, n);  
        sum = Min = cnt;  
        rep(i, n) {  
            sum = sum - b[i] + (n - 1 - b[i]);  
            Min = min(Min, sum);  
        }  
        printf("%d\n", Min);  
    }  
    return 0;  
}