自动搬运

查看原文

来自洛谷，原作者为

	Christmas_Defunct 垃圾中考

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

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

以下是正文

很简单的分类讨论题，赛时 AC 了。

题意简化

你可以对序列 $a$ 进行如下两类操作 $k(k\in\N^+)$ 次。

1. 交换 $a_i$ 和 $a_j$，其中 $i\not=j$。
2. 删除 $a_i\sim a_j$，但是必须满足 $a_i=a_j$。

显然的，有 $+\infty$ 种方法可以使 $a$ 为空串，现在想知道所有方法中 $\min k$ 的大小。

解法

这题求 $\min k$ 的做法很显然：使操作 $2$ 的效率最大化，因为只有操作 $2$ 可以删除数，而操作 $1$ 却无法删除。

这时候问题聚焦于另一个地方：如何使操作 $2$ 的效率最大化呢？

注意到 $a_i=a_j$，所以可以猜测做法为通过操作 $1$ 构造满足 $a_1=a_n$ 的序列，这样的话就可以满足仅需修改首尾便可满足操作的 $2$ 条件。

这里，我们只需要分析 $a_1$ 和 $a_n$。

1. 若 $a_1=a_n$，进行 $1$ 次操作 $2$ 即可，$\min k=1$。
2. 若 $a_1\not=a_n$，继续分类讨论。

   记 $b_{a_{i}}$ 为 $a_i$ 在序列中出现的次数。

   1. 若 $b_{a_1}\geq2$，记另外任意一个值为 $a_1$ 且在 $a$ 中出现的数的位置为 $pos_l$，进行一次操作 $1$，交换 $a_{pos_l} 和 a_{n}$，随即转换为 $a_1=a_n$，故 $\min k=2$。
   2. 若 $b_{a_n}\geq2$，记另外任意一个值为 $a_n$ 且在 $a$ 中出现的数的位置为 $pos_r$，进行一次操作 $1$，交换 $a_{pos_r} 和 a_{1}$，随即转换为 $a_1=a_n$，故 $\min k=2$。
   3. 若不满足 $b_{a_1}\geq2$ 和 $b_{a_n}\geq2$ 但是 $\exist\ b_{a_i}\ge2$，此时记 $pos_l$ 和 $pos_r$ 为其中相异的两个值为 $a_i$ 的数的下标，进行 $2$ 次操作 $1$，分别交换 $a_1,a_{pos_l}$ 和 $a_n,a_{pos_r}$，随即转换为 $a_1=a_n$，故 $\min k=3$。
   4. 若 $\forall\ b_{a_i}=1$，则无论如何进行多少次操作 $1$ 都无法转化为 $a_1=a_n$，此时只能使 $i=j$，必定满足 $a_i=a_j$，有 $n$ 个数，所以此时 $\min k=n$。

这样，我们便完成了分类讨论，下面进行整理。

整理得

• 若 $a_1=a_n$，$\min k=1$；
• 若 $b_{a_1}\geq2$ 或 $b_{a_n}\geq2$，$\min k=2$；
• 若 $\exist\ b_{a_i}\geq2(i\not=1,n)$，则 $\min k=3$；
• 否则 $\min k=n$。

这里的 $b$ 又被称之为桶数组，用了空间换时间的优化方法。用 $\mathcal{O}(\max a)$ 的空间换掉了 $\mathcal{O}(n)$ 的时间。此时空间复杂度为 $\mathcal{O}(\max a)$，时间复杂度为 $\mathcal{O}(n)$。时间上可以通过 $n=10^5$ 的数据，但是无法满足 $\max a=10^9$。

注意到 $a_i$ 的数量最多为 $n$ 个，所以用离散化可以去掉多占用的空间，将空间复杂度优化至 $\mathcal{O}(n)$，此处仅使用 map 进行优化即可，此处不再赘述 map 的使用方法，不会用的可以参考别的文章。

综上，我们的每个过程复杂度变化如下：

• 时间复杂度：$\mathcal{O}(n^2)\to\mathcal{O}(n)\to\mathcal{O}(n)$。
• 空间复杂度：$\mathcal{O}(n)\to\mathcal{O(\max a)}\to\mathcal{O}(n)$。

代码

下面是本题的代码，请勿抄袭，这么简单的题目咱还是别抄了。

#include <bits/stdc++.h>
using namespace std;

void work() {
	int n, a[100005];
	bool flag = false;
	cin >> n;
	map<int, int> mp;
	memset(a, 0, sizeof a);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mp[a[i]]++;
		if (mp[a[i]] == 2) flag = true;
	}
	if (mp[a[1]] >= 2 || mp[a[n]] >= 2) {
		if (a[1] == a[n]) cout << 1 << '\n';
		else cout << 2 << '\n';
	} else if (mp[a[1]] == 1 && mp[a[n]] == 1) {
		if (flag) cout << 3 << '\n';
		else cout << n << '\n';
	}
}

signed main() {
	int t;
	cin >> t;
	while (t--) work();
	return 0;
}

此文是本人的第 $2$ 篇题解，欢迎参考！