学步园

逆序数的题目还是用树状数组写比较好 

先把原序列逆序数求出来。

按题意模拟一下求出最小的逆序。

接下来就是推一下

按题目意思

n 个数 如果a 是第一个元素 那么小于a 的有a 个 (题目给的数据从0 开始)

当a 放到最后 n - 1元素 逆序数  -1 。

a 前面比a 大的元素有 n - a - 1 

那么a 的逆序数就是 n - a - 1

所以 a的逆序数s =   a  * -1 + n - a - 1

就是进行一次操作的 数列的逆序数在加上之前的

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int const MAXN = 5010;
int c[MAXN+10],a[MAXN];
inline int Min(int a,int b){
    return a<b?a:b;
}
int LowBit(int x){
    return x & (-x);
}
void Add(int x,int d){
    while(x<= MAXN){
        c[x] += d;
        x += LowBit(x);
    }
}
int Sum(int x){
    int ret = 0;
    while(x > 0){
        ret += c[x];
        x -= LowBit(x);
    }
    return ret;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        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);
            //树状数组不能有0 否则会跪
        }
        int cnt = sum;
        for(int i = 1;i <= n;i++){
            sum += n - 2 * a[i] - 1;
            cnt = Min(cnt,sum);
        }
        printf("%d\n",cnt);

    }
    return 0;
}