「ALFR Round 3」B Swap & Delete 题解

· · 题解

很简单的分类讨论题，赛时 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。

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

整理得

这里的 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 的使用方法，不会用的可以参考别的文章。

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

代码

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

#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 篇题解，欢迎参考！