Description

Solution

首先要发现一个事实：对于每个不再正确位置上的人，我们都要花费1的代价来让他正确（然而我没有发现…）。

TODO:证明这个事实。

然后就可以转化问题为：最多有多少个人不用动。那么那些人不用动呢？就是那些与目标位置距离相等的人的集合，即断环为链之后，不用右移就在目标位置的人、右移一次到达目标位置的人、右移两次……这几群人。他们之中最多的那群就是最多有多少个人不用移动。

如何生成目标链呢？直接模拟就好了。不过要注意如果“我爱的人不爱我”的话就gg了。

Code

#include 
    
     #include 
     
      const int N = 50010;int fr[N][2], per[N];int n;int spin[N];int main() {    scanf("%d", &n);    for (int i = 1; i <= n; ++i) scanf("%d%d", &fr[i][0], &fr[i][1]);    // 计算完美的序列      for (int i = 1; i <= n; ++i) {        if ((i != fr[fr[i][1]][0] && i != fr[fr[i][1]][1])         || (i != fr[fr[i][0]][0] && i != fr[fr[i][0]][1])) {            puts("-1");            return 0;        }    }    per[1] = 1; per[2] = fr[1][0]; per[n] = fr[1][1];    for (int i = 2; i < n; ++i) {        if (per[i-1] == fr[per[i]][0]) {            per[i+1] = fr[per[i]][1];        } else {            per[i+1] = fr[per[i]][0];        }    }    // 由于我们恢复每个点的代价为1，所以找出哪些点不用动，剩下的就是答案。    int ans = 0x3f3f3f3f;    for (int i = 1; i <= n; ++i) {        if (++spin[(per[i] - i + n) % n] > n - ans) {            ans = n - spin[(per[i] - i + n) % n];        }    }       memset(spin, 0, sizeof spin);    for (int i = 1; i <= n; ++i) {        if (++spin[(per[i] + i - 1) % n] > n - ans) {            ans = n - spin[(per[i] + i - 1) % n];        }    }    printf("%d\n", ans);    return 0;}