模拟 30pts $n^2$

算法分析

算法分析，通过输入的关系利用dfs序，得到目标链,假设有$k$个数在当前链和目标链中的位置相同，那么就有$n-k$个不相同的，我们每次操作只对这$n-k$个数进行，我们最优可以做到每操作$x$个数，就一次性把这$x$个数全放到正确位置上，比如说: 1 2 3 4 5 6 7 8 9 10 1 8 2 7 5 3 6 4 10 9 先通过(10,8,1)->8 2 3 4 5 6 7 10 9 1 再通过(3,5,4,7)就可以了。 (注意是环:8 2 7 5 3 6 4 10 9 1和1 8 2 7 53 6 4 1 0 9 是一样的)这样就做到了每次只操作位置不对的，实现了最小化代价。 所以，结论就是:把初始链变成目标链的最小代价为$n-k$。($k$的意义同上)那么我们只需要$O(n)$搞出目标链的两种情况，然后每次右移(左移)之后与1,2,3.n作对比，求得最小的$n-k$。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int n;
int e[N][2]; //存图
int q[N],cnt; //dfs序
bool st[N]; 
void dfs(int u) //构造目标环
{
    st[u]=true;
    q[cnt++]=u;
    for(int i=0;i<2;i++)
    {
        int j=e[u][i];
        if(!st[j]) dfs(j);
    }
}
bool check()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<2;j++)
        {
            int x=e[i][j],t=0;  
            for(int k=0;k<2;k++)
            {
                if(e[x][k]==i) //相互可以走到
                {
                    t=1;
                }
            }
            if(!t) return false; //出现了走不到的情况
        }
    }
    dfs(1); //开始构造目标环
    if(cnt<n) return false; //存在多个环
    return true;
}
int work()
{
    reverse(q,q+n); //反转一遍
    int res=0;
    for(int i=1;i<=n;i++) //旋转初始位置
    {
        int t=i;
        int cnt=0;
        for(int j=0;j<n;j++) //统计旋转以后相同的数目
        {
            if(t==q[j])
            {
                cnt++;
            }
            t++;
            if(t==n+1) t=1; //转完一圈
        }
        res=max(res,cnt);
    }
    
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>e[i][0]>>e[i][1];
    }
    if(!check()) cout<<-1; //不满足
    else
    {
        cout<<n-max(work(),work()); //总的数目减去最少的相同数目
    }
    return 0;
}

100pts O(n)

算法分析

实际上我们在得到目标环了以后，我们可以通过统计得到对应位置上数需要旋转几次得到，然后旋转次数最多的就是最后的答案了。

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int n;
int e[N][2]; //存图
int sum[N];
int q[N],cnt; //dfs序
bool st[N]; 
void dfs(int u) //构造目标环
{
    st[u]=true;
    q[cnt++]=u;
    for(int i=0;i<2;i++)
    {
        int j=e[u][i];
        if(!st[j]) dfs(j);
    }
}
bool check()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<2;j++)
        {
            int x=e[i][j],t=0;  
            for(int k=0;k<2;k++)
            {
                if(e[x][k]==i) //相互可以走到
                {
                    t=1;
                }
            }
            if(!t) return false; //出现了走不到的情况
        }
    }
    dfs(1); //开始构造目标环
    if(cnt<n) return false; //存在多个环
    return true;
}
int work()
{
    reverse(q,q+n); //反转一遍
    memset(sum,0,sizeof sum);//清空
    
    int res=0;
    for(int i=0;i<n;i++)
    {
        int j=q[i],k=i+1;
        int d=k-j;//需要移动的次数
        if(d<0) d+=n;//其实是移动到n+k-j
        sum[d]++;
        res=max(res,sum[d]);
    }
    
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>e[i][0]>>e[i][1];
    }
    if(!check()) cout<<-1; //不满足
    else
    {
        cout<<n-max(work(),work()); //总的数目减去最少的相同数目
    }
    return 0;
}