历尽千辛万苦终于过了这个题…
根据题意可以很简单地整理出目标环
题目中给的交换操作可以让任何一个人到他想要去的位置去
所以简化题意,就是求最少需要变动多少个人,使初始环变为目标环
开始位置就重合的不用动,其他的都需要变动
可以通过转动目标环来让重合的人数变多,枚举转动再求的复杂度是n^2,无法接受
考虑破环成链
可以发现目标环因为可以旋转所以无所谓正逆,而初始环可以有顺时针和逆时针两种表示法
顺时针就是1,2,3,…,n 逆时针是 1,n,n - 1,....,2
一个重要的性质是:转动目标环时所有的点距离重合位置的变化一定是同步的
所以可以通过转动同时重合的点距离重合位置的距离一定相同
直接算出不同距离的点数,找出最多重合的点数
逆时针类似地作一遍取最大值,最后用总点数减去最大重合点数即可
#include <iostream>
#include <cmath>
using namespace std;
const int N = 50010;
int ans,h[N],n,l[N],r[N],num1[N],num2[N];
bool used[N];
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++)
scanf("%d%d",&l[i],&r[i]);
h[1] = num1[0] = num1[n] = num2[0] = num2[n] = used[1] = 1;
for(int i = 2;i <= n;i ++)
{
if(!used[l[h[i - 1]]])h[i] = l[h[i - 1]];
else if(!used[r[h[i - 1]]])h[i] = r[h[i - 1]];
else {puts("-1");return 0;}
used[h[i]] = 1;
ans = max(++ num1[(h[i] - i + n) % n],ans);
ans = max(++ num2[(h[i] - (n - i + 2) + n) % n],ans);
}
cout << n - ans;
}