题解：首先是很基础的树状数组求逆序对，然后对于每一个第一个数往后移动，对于逆序数的贡献是n-a[i]-1-a[i]。枚举然后求最小值即可。

#include <cstdio>#include <iostream>#include <algorithm>using namespace std;int n,c[5001],x,a[5001];int add(int x){while(x<=n)c[x]++,x+=x&-x;}int sum(int x){int s=0;while(x>0)s+=c[x],x-=x&-x;return s;}int main(){    while(~scanf("%d",&n)){        int ans=0;        memset(c,0,sizeof(c));        for(int i=0;i<n;i++){            scanf("%d",&a[i]);            ans+=(i-sum(a[i]+1));            add(a[i]+1);        }int tmp=ans;        for(int i=0;i<n-1;i++){            tmp=tmp-a[i]+n-a[i]-1;            ans=min(ans,tmp);        }printf("%d\n",ans);    }    return 0;}