hdu1394

传送门

本题就是求循环移位后逆序数的最小值。
其实主要就是求序列的逆序数。
逆序数的求法很多，可以用归并排序求。
也可以用树状数组和线段树求逆序数。

逆序数求得之后，把第一个数移到最后的逆序数是可以直接得到的。
比如原来的逆序数是ans，把a[0]移到最后，减少逆序数a[0]，同时增加逆序数n-a[0]-1个，就是ans-a[0]+n-a[0]-1；

只要i从0-n-1循环一遍取最小值就可以了。

代码

树状数组(AC)：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 5050;
int n, e[maxn];

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

void add(int k, int v){
    while(k <= n){
        e[k] += v;
        k += lowbit(k);
    }
}

int sum(int k){
    int re = 0;
    while(k > 0){
        re += e[k];
        k -= lowbit(k);
    }
    return re;
}

int a[maxn];

int main(){
    while(~scanf("%d", &n)){
        int ans = 0;
        memset(e, 0, sizeof(e));
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            a[i]++;
            ans += sum(n) - sum(a[i]);
            add(a[i], 1);  //注意这里e[k]并没有初始化为a[k]，而是用到了类似差值的思想
        }
        int Min = ans;
        for(int i = 1; i <= n; i++){
            ans += n - a[i] - (a[i] - 1);
            if(ans < Min) Min = ans;
        }
        printf("%d\n", Min);
    }
    return 0;
}