题解：P1053 [NOIP 2005 提高组] 篝火晚会

· · 题解

\color{blue}{\texttt{[Analysis]}}

话说这题和贪心、图论有什么关系。

不过这种题目是我的死穴。

我们首先证明如下结论：如果目标状态和初始状态有 x 个人位置失配，则一定可以通过 x 的代价调整回来。

我们考察其中一个失配的同学 \alpha_{1}，假设 Ta 最终应该在的位置是 \beta_{1}，现在所在的位置是 \xi。

如果有解的情况下，那么 \beta_{1} 位置上的同学 \alpha_{2} 一定也是失配的（不然就无解了）。假设 \alpha_{2} 同学最终应该在 \beta_{2} 位置。

  • 如果 \beta_{2}=\xi，即 \alpha_{1},\alpha_{2} 两名同学刚好错开，那么我们可以通过一次 m=2 的操作使得 2 个失配的人都回到应该在的位置。
  • 如果 \beta_{2} \not = \xi，那么我们继续考察在 \beta_{2} 位置的同学 \alpha_{3}，然后假设 \alpha_{3} 最终应该在的位置 \beta_{3}。如果 \beta_{3}=\xi，那么我们可以通过一次 m=3 的操作 \{ \alpha_{1},\alpha_{2},\alpha_{3} \}，通过 3 的代价使得 3 个失配的同学回到应该在的位置。
  • 如果还不行，继续按照这个规则考察 \alpha_{4},\beta_{4},\alpha_{5},\beta_{5},\cdots,\alpha_{k},\beta_{k}，其中 \beta_{k}=\xi。可以证明 k 一定是存在的，因为人数是有限的，最多就是 n 个人全部进来了。可以通过一次 m=k 的操作 \{ \alpha_{1},\alpha_{2},\cdots,\alpha_{k} \} 使得 k 个失配的同学回到应该在的位置。

这里的证明倒是有一点图论的味道，最终失配的同学按照上述规则可以形成若干个环，而每个环可以通过一次代价为环大小的操作复原。因此证明了所需的结论。

那么现在问题就变成了，究竟最少有多少个人失配。

根据输入，我们可以确定最后环的形态。

环是没有头尾的，当然可以强制定义一个头尾，即强制第 i 个同学在序列的开头，检查有多少个人失配，但是这样做是 O(n^{2}) 的。

我们还是考虑以 1 作为序列的开头。把初始链和目标链对应位作减法，将会得到一个数列 \text{tmp}_{1 \dots n}。

旋转目标链和旋转初始链是等价的，我们考虑旋转初始链。

由于初始链是 1,2,3,\dots,n，因此旋转之后，除了末尾特殊位置之外，其它位置的 \text{tmp} 值都同样的增大或减小了 1。也就是说，如果两个位置 x_{1},x_{2}，它们是适配的，即它们无需做操作，则 \text{tmp}_{x_{1}},\text{tmp}_{x_{2}} 的差将保持不变。

我们也知道，在初始链旋转到某一个位置时，如果一个位置的 \text{tmp}_{i}^{'}=0，那么这个位置在这个初始链下是适配的，无需做操作的。因此我们可以统计 \text{tmp}_{i} 里的众数出现的次数，然后我们根据上一段的性质可以通过旋转初始链使得众数都变为 0，那么适配的人数不就最多了吗。

因此，一个 O(n) 的算法就产生了。

注意链的方向对答案是有影响的，需要顺反做两次。

\color{blue}{\text{Code}} 
int Clock[N],Counter[N],ans;
int n,anti[N][2],target[N],init[N];

int main(){
    n=read();
    for(int i=1;i<=n;i++){
        anti[i][0]=read();
        anti[i][1]=read();

        init[i]=i;
    }

    target[1]=1;
    target[2]=anti[1][0];
    for(int i=2;i<n;i++){
        if (target[i-1]==anti[target[i]][0])
            target[i+1]=anti[target[i]][1];
        else if (target[i-1]==anti[target[i]][1])
            target[i+1]=anti[target[i]][0];
        else{
            printf("-1");
            return 0;
        }//你喜欢人家，人家不喜欢你 
    }//构造目标链

    for(int i=1;i<=n;i++){
        Clock[(target[i]-init[i]+n)%n]++;
        Counter[(target[i]-init[n-i+1]+n)%n]++;
    }

    for(int i=0;i<n;i++)
        ans=max(ans,max(Clock[i],Counter[i]));

    return printf("%d",n-ans)*0;
}