题解 P6709 【[CCC2020 T4] Swapping Seats】

· · 题解

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

原题链接：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