Luogu

分析

考试时因为有个距离算错结果没有A qwq

首先可以$O(n)$构造出目标环,同时判断这个环是否存在。

具体的判断方法是判断相邻的两个点的相邻点中有没有这个点。

然后比较这个环和初始环,发现有一些位置不同。

分析一些数据,猜结论:从初始环到目标环的最小代价就是两个环位置不同的数的个数。

30分算法

因为是环,所以可以$O(n^2)$比较,然后取最小。

100分算法。

发现环的一个性质:转一下后,原来距离相等的还是距离相等。

举个例子:

1 2 3 4
1 3 2 4

把下面那个环转一下后:

1 2 3 4
2 4 1 3

原来1到1、4到4的距离是相等的,转一下后仍然相等。

但是这样子要求不匹配的比较难搞。考虑正难则反,求匹配的。

所以只要算出向左和向右的距离。

比如向左的距离是$L$,向右的距离是$R$,那么$dis1[L]++,dis2[R]++$。

然后答案就是$n-max_{i=0}^{n-1}\{max\{dis1[i],dis2[i]\}\}$

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[50010],b[50010];
int l[50010],r[50010];
int vis[50010];
int dis1[50010],dis2[50010];

int main() {
    int n=read();
    for (re int i=1;i<=n;i++) l[i]=read(),r[i]=read(),a[i]=i;
    for (re int i=1;i<=n;i++) {
        if (l[l[i]]!=i&&r[l[i]]!=i) { puts("-1"); return 0; }
        if (l[r[i]]!=i&&r[r[i]]!=i) { puts("-1"); return 0; }
    }
    int now=1;
    for (re int i=1;i<=n;i++) {
        vis[now]=1,b[i]=now;
        if (vis[l[now]]) now=r[now];
        else now=l[now];
    }
    for (re int i=1;i<=n;i++) {
        dis1[(b[i]-a[i]+n)%n]++;
        dis2[(a[i]+b[i])%n]++;
    }
    int ans=-1;
    for (re int i=0;i<n;i++) ans=max(ans,max(dis1[i],dis2[i]));
    printf("%d\n",n-ans);
    return 0;
}
最后修改:2019 年 05 月 28 日 08 : 42 PM