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

发表评论

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

你是机器人吗? =。= *