题解：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}}

CPP

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;
}

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

文章操作

相关推荐

评论

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