hdu 1394(BIT求逆序數)

題意：有長度為n的序列，序列的數字是0～n-1組成，然後這個序列可以看做環，那麼就有n個長度為n的序列，問n個序列裡最小逆序數是多少。
題解：先把初始序列的逆序數算出來，然後移動每一個開頭數字a到後面，逆序數變化的是比a大的數字逆序數加一，比a小的逆序數減一，所以按這個規律再循環一次找最小值就可以了。

#include 
#include 
#include 
using namespace std;
const int N = 5005;
int n, C[N], a[N];

int lowbit(int x) {
    return x & (-x);
}

int Sum(int x) {
    int ret = 0;
    while (x > 0) {
        ret += C[x];
        x -= lowbit(x);
    }
    return ret;
}

void Add(int x, int d) {
    while (x <= n) {
        C[x] += d;
        x += lowbit(x);
    }
}

int main() {
    while (scanf(%d, &n) == 1) {
        memset(C, 0, sizeof(C));
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf(%d, &a[i]);
            Add(a[i] + 1, 1);
            sum += i - Sum(a[i] + 1);
        }
        int res = sum;
        for (int i = 1; i < n; i++) {
            sum = sum + ((n - 1 - a[i]) - a[i]);
            res = min(res, sum);
        }
        printf(%d
, res);
    }
    return 0;
}