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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注