传送门

题目大意

Solution

本题较为简单，随便口胡一下就好了。 我们随手选一个方法，先求出原序列的逆序对，然后每一次平移可以看作是从序列头部删掉一个，从序列的尾部加入一个，所以说我们可以看出来（手玩几组数据就可以看出规律来）， 如果当前要移动$a$，那么原序列逆序对数会减少$a-1$个，随后会增加$n-a$个，所以说直接循环跑一边最大值就好了。 代码如下：

#include<bits/stdc++.h> using namespace std; const int maxn=10005; int bit[maxn],a[maxn],n; inline int lowbit(int x){ return x&-x; } inline void update(int k,int x){ for(int i=k;i<=n;i+=lowbit(i)) bit[i]+=x; } inline int query(int k){ int ret=0; for(int i=k;i;i-=lowbit(i)) ret+=bit[i]; return ret; } int main(){ while(scanf("%d",&n)==1){ for(int i=1;i<=n;i++) bit[i]=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); int sum=0; for(int i=n;i>=1;i--){ update(a[i]+1,1); sum+=query(a[i]); } int ans=sum; for(int i=1;i<=n;i++){ sum=sum-a[i]+(n-a[i]-1); ans=min(ans,sum); } printf("%d\n",ans); } return 0; }