1. 题目

传送门=￣ω￣=

题目大意：
一个由 0..n-1 组成的序列，每次可以把队首的元素移到队尾，求形成的 n 个序列中最小逆序对数目

2. 题解

直接 $O(n^2)$算法就过了
如果当前列首元素为 a，那么列中比它小的数的个数就是 a，比它大的数的个数就是 n-a-1，那么把它移动到列尾，减少了 a 个逆序对，增加了 n-a-1 个逆序对
所以就可以直接递推了

代码：

#include <bits/stdc++.h>
using namespace std;
int n,a[5005],cnt,ans;
int main()
{
    while(cnt=ans=0,~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)if(a[i]>a[j])cnt++,ans++;
        for(int i=1;i<=n;i++)cnt+=n-1-(a[i]<<1),ans=min(ans,cnt);
        printf("%d\n",ans);
    }
    return 0;
}