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;
}