自动搬运

查看原文

来自洛谷，原作者为

	yx666 幸会，OI。OI，幸会 。

搬运于2025-08-24 23:01:45，当前版本为作者最后更新于2024-08-04 17:52:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10840 题解

给你一个序列 $a_1, a_2, \ldots, a_n$。你可以对这个序列进行若干次操作。

设一次操作前序列长度为 $m$，那么这次操作你可以选择一个整数 $i$ 使得 $1 \le i \le m - 1$ 且 $a_i \ne a_{i + 1}$，删除 $a_{i + 1}$ 并把 $a_i$ 的值设成任意整数。

求最多能进行多少次操作。

对于所有数据，满足 $1 \le n \le 10^5$，$1 \le a_i \le 10^9$。

先说结论。

结论

1. 如果 $\forall i\in[1,n-1],a_i=a_{i+1}$（即所有 $a_i$ 都相等），答案为 $0$。

2. 否则，答案为 $n-1$。

证明

结论 1，证明显然。

对于结论 2，归纳法可证（记 $f(i)$ 表示长度为 $i$ 时，至少存在一对不等的相邻数时，最大操作次数）：

• $n=1$ 时，$f(1)=0$，结论成立。

• $n>1$ 时，$f(n)=f(n-1)+1$，结论成立。因为我们可以通过每次操作，留下至少一对不等的相邻数（对于每次操作的 $i$，都将 $a_i$ 修改为一个没有出现过的数）。

signed main(){
	int n=read(),tp=read();
	for(int i=1;i<n;++i){
		int t=read();
		if(t!=tp){
			printf("%d",n-1);
			return 0;
		}
	}putchar('0');
	return 0;
}