题解 P1053 【篝火晚会】

· · 题解

模拟

P1053 先解决-1的情况，如果可以完全实现同学们的愿望，那么每两个相邻同学一定互相喜欢，不满足这个条件肯定不能完全实现同学们的愿望。

然后就是可行的情况，先把所期望的环的关系存储起来，用数组实现。当然期望环有两种情况，若视第一种情况为顺时针，那么第二种情况为逆时针：

输入：    第一种情况：    第二种情况：
4          1              1
3 4       4 3            3 4
4 3        2              2
1 2
1 2

设期望环中编号为1的同学所在的位置为1，往右依次为2,3,\cdots,n（n在1的左边），则只需存储一种情况，另一种情况可以推出：位置i(2\leq i\leq n)上的同学在第二种情况中位置为n-i+2。由于是环形数据，因此无论怎么旋转原数据，得到的新环与原环都是等价的：

 1     3
4 3   1 2
 2     4

环一  环二

显然环一与环二是相同的。因此，我们可以将初始环（1到n顺序排列的环）中编号为i的同学的位置记为i，统计编号为i的同学顺时针移动到期望环中其所在位置要经过的单位长度，例如编号为3的同学：

初始环：
    1
   4 2
    3

期望环第一种情况：经过3个单位长度
期望环第二种情况：经过1个单位长度

在同一种情况中经过相同单位长度的同学，我们可以把他们看做一个整体，这个整体是静止的（整体内部同学不会相对移动）。例如在第二种情况中可以把编号为2和3的同学当作一个整体（它们都要经过1个单位长度），则编号为2和3的同学可以不移动，让编号为1和4的同学来移动，调整为期望环。题目要求输出移动的最少次数，也就是最少的必须移动的同学数。要满足移动的同学最少，就要保证静止的同学最多，也就是最大整体，那么，我们要计算经过单位长度相同的最多同学数，剩余的同学（需要移动的同学）数就是答案。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4*5+5;
typedef int INT_N[N];
INT_N want_1,list_1,want_2,list_2,expect;
int n;
inline void read(int&number){
    int un=1;
    char letter=getchar();
    number=0;
    while(letter<'0'||'9'<letter){
        un=letter^'-'?1:-1;
        letter=getchar();
    }
    while('0'<=letter&&letter<='9'){
        number=(number<<1)+(number<<3)+letter-'0';
        letter=getchar();
    }
    number*=un;
}//快速读入
void init(){
    read(n);
    for(register int i=1;i<=n;i++)
        read(want_1[i]),read(want_2[i]);
    for(register int i=1;i<=n;i++)
        if(want_1[want_1[i]]^i&&want_2[want_1[i]]^i||want_1[want_2[i]]^i&&want_2[want_2[i]]^i){
            printf("-1\n");
            exit(0);
        }//当前同学希望的两个同学中如果有不希望当前同学的，不满足双向希望性，即不能满足每个同学的希望
    expect[2]=want_1[expect[1]=1],expect[n]=want_2[1];//初始化期望环
    for(register int i=2;i<n-1;i++)
        expect[i+1]=want_1[expect[i]]^expect[i-1]?want_1[expect[i]]:want_2[expect[i]];//构造期望环
}
void work(){
    int Max=0;
    for(register int i=1;i<=n;i++)
        list_1[(i+n-expect[i])%n]++,list_2[((n<<1)-i+2-expect[i])%n]++;//(i+n-expect[i])%n表示第一种情况，期望环中编号为i的同学经过的单位长度，((n-i+2)+n-expect[i])%n表示第二种情况，期望环中编号为n-i+2的同学经过的单位长度
    for(register int i=0;i<n;i++)
        Max=max(Max,max(list_1[i],list_2[i]));//表示更新经过单位长度为i的同学数（两种情况）
    printf("%d\n",n-Max);
}
int main(){
    init();
    work();
    return 0;
}