自动搬运

查看原文

来自洛谷，原作者为

	gznpp 星星夜月引路 爱带我回家

搬运于2025-08-24 22:23:17，当前版本为作者最后更新于2020-11-02 11:19:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

本题解在博客页面显示正常。

原题链接：https://dmoj.ca/problem/ccc20s4

CCC 2020 题组：https://cemc.math.uwaterloo.ca/contests/computing/2020/ccc/seniorEF.pdf

本题解默认排序为从小到大排。

题意：给定一个 $N$ 元环，环上值域只有 $3$，现要求值相同的元素必须在环上相邻，求最少交换次数。

首先，考虑一下交换次数问题。

可以看看 USACO Training 的 Sorting a Three-Valued Sequence 这题，洛谷 P1459。

记：不在 排序之后 $d$ 的范围的 $d$ 的个数为 $Non_d$。如 1 3 2 1 中 $Non_1 = 1, Non_2 = 0, Non_3 = 1$；

记：在排序之后 $f$ 的范围的 $e$ 的个数为 $Num_{e, f}$。如 1 3 1 2 中 $Num_{1, 3} = 0, Num_{3, 1} = 1, Num_{1, 1} = 1$。

它启示我们：

值域仅为 $2$ 的排序，交换次数就是：$Non_1 = Non_2 = Num_{1, 2} = Num_{2, 1}$。我们本应该大动干戈把不在范围中的 $1$ 和 $2$ 全都交换到应该在的位置，答案为 $Non_1 + Non_2$；但这是交换，可以省下 $\min(Num_{1, 2}, Num_{2, 1})$ 的操作次数。因为 $1, 2$ 之间交换，换好一个 $2$ 的同时就把一个 $1$ 换好了。故正确答案为 $Non_1 + Non_2 - \min(Num_{1, 2}, Num_{2, 1})$，也就是前面那一堆。

推广到值域为 $3$ 的排序，交换次数还是：$Non_1 + Non_2 - \min(Num_{1, 2} + Num_{2, 1})$。$3$ 跟 $1, 2$ 交换当然能省次数，但是我们只用考虑 $1$ 跟 $2$ 换好就行了，因为这样 $3$ 一定换好了。

又因为这是个环，所以枚举 $1$（这里是 A）的起始位置，同时破环成链用前缀和维护前 $i$ 个元素中分别有多少个 A, B, C 即可。注意还要讨论一下 A 后面跟的是 B 还是 C，因为本题 A, B, C 的排列顺序不定。时间复杂度 $O(n)$。

这里还有一个小技巧，同时可以拓展一下思维。我们可以稍微化简一下式子。（这里 B 和 C 是对称的，只写一个）

$$\begin{aligned} & Non_A + Non_B - \min(Num_{A, B} + Num_{B, A})\\ =& Num_{A, B} + Num_{A, C} + Num_{B, A} + Num_{B, C} - \min(Num_{A, B} + Num_{B, A})\\ =& \max(Num_{A, B} + Num_{B, A}) + Num_{A, C} + Num_{B, C}\\ =& \max(Num_{A, B} + Num_{B, A}) + Non_C \end{aligned} $$

可以稍微简化一点代码。

Code:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000002;
int n, sa[maxn], sb[maxn], sc[maxn], suma, sumb, sumc, ans = INT_MAX;
char a[maxn];

int mo(int x) { return x % (n + 1) + 1; }

signed main() {
	scanf("%s", a + 1); n = strlen(a + 1);
	for (int i = n + 1; i <= (n << 1); ++i)
		a[i] = a[i - n];
	for (int i = 1; i <= n; ++i)
		if (a[i] == 'A') ++suma;
		else if (a[i] == 'B') ++sumb;
		else ++sumc;
	for (int i = 1; i <= (n << 1); ++i) {
		sa[i] = sa[i - 1] + (bool)(a[i] == 'A');
		sb[i] = sb[i - 1] + (bool)(a[i] == 'B');
		sc[i] = sc[i - 1] + (bool)(a[i] == 'C');
	}
	for (int i = 1; i <= n; ++i) { // positions for A begins
		int nx1 = i + suma, nx2;
		// B is next
		nx2 = nx1 + sumb;
		ans = min(ans, max(sb[nx1 - 1] - sb[i - 1], sa[nx2 - 1] - sa[nx1 - 1]) + sumc - sc[i + n - 1] + sc[nx2 - 1]);
		// C is next
		nx2 = nx1 + sumc;
		ans = min(ans, max(sc[nx1 - 1] - sc[i - 1], sa[nx2 - 1] - sa[nx1 - 1]) + sumb - sb[i + n - 1] + sb[nx2 - 1]);
	}
	return cout << ans << endl, 0;
}

参考 DMOJ 官方题解：https://dmoj.ca/problem/ccc20s4/editorial