hdu 1394 Minimum Inversion Number(树状数组)

题目链接:hdu Minimum Inversion Number

题目大意：给定一个序列，求该序列所有的循环序列中，逆序对数的最小值。

解题思路：先预处理出原先序列的逆序对数，然后后面的循环序列都可以用o(1)的复杂度递推得到。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 5005;
#define lowbit(x) ((x)&(-x))

int N, arr[maxn], fenw[maxn];

void add (int x, int v) {
    while (x <= N) {
        fenw[x] += v;
        x += lowbit(x);
    }
}

int sum(int x) {
    int ret = 0;
    while (x) {
        ret += fenw[x];
        x -= lowbit(x);
    }
    return ret;
}

int main () {
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            scanf("%d", &arr[i]);
        memset(fenw, 0, sizeof(fenw));

        int s = 0;
        for (int i = N - 1; i >= 0; i--) {
            s += sum(arr[i] + 1);
            add(arr[i] + 1, 1);
        }

        int ans = s;
        for (int i = 0; i < N; i++) {
            s = s + N - arr[i] * 2 - 1;
            ans = min(s, ans);
        }
        printf("%d\n", ans);
    }
    return 0;
}