hdu 1394 Minimum Inversion Number(树状数组)

传送门：点击打开链接

题目大意：

给你一个0~n-1的全排列，每次将最前面的数移动到最后。每次操作结束之后，求这个序列的全排列的逆序数。

问 所有操作结束之后的逆序数和的最小值是多少。

解题思路：

容易想到树状数组求逆序数。现在考虑移动。

当将最前面的值移动到末尾时，其实增加了大于它的值的逆序对的个数（因为那些大于它的都在他前面了），同时又减少了小于他的值的逆序数的个数（因为本来它在最前面，所有小于它的值都在他后面）。所以，其实每次移动 逆序数的变化是增加了：n-a[i]，同时减少了a[i]-1。

至于为什么要将所以的值增加1.原因是树状数组要求。23333

#include <cstdio>
#include <cstring>
#define maxn 5050
int C[maxn];
int a[maxn];

inline int lowbit(int x)
{
    return x&-x;
}
void add(int x)
{
    while(x < maxn)
    {
        C[x]++;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int res = 0;
    while(x > 0)
    {
        res += C[x];
        x -= lowbit(x);
    }
    return res;
}
int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        memset(C,0,sizeof C);
        for(int i = 1;i <= n;i++)
        {
            scanf("%d",&a[i]);
            a[i]++;
        }
        int res = 0;
        for(int i = 1;i <= n;i++)
        {
            add(a[i]);
            res += sum(n)-sum(a[i]);
        }
        int ans = res;
        for(int i = 1;i < n;i++)
        {
            res += (n-a[i])-(a[i]-1);
            ans = ans<res?ans:res;
        }
        printf("%d\n",ans);
    }
    return 0;
}