Epic Transformation - 题解

比赛与标签

比赛: Codeforces Round 710 (Div. 3) 标签: constructive algorithms, data structures, greedy 难度: *1400

喵喵，题目说什么呀？

喵~ 主人，今天我们来解决一个超级有趣的问题呐！(ฅ'ω'ฅ)

是这样的：我们拿到一个有 n 个整数的数组 a。我们可以对它施展一个神奇的魔法：

1. 从数组里挑出两个 值不相同 的数字，a_i 和 a_j。
2. 然后“咻”的一下，把这两个数字从数组里拿走！

这个魔法可以施展任意多次。我们的任务是，通过这个魔法，让数组里剩下的数字尽可能少。最后，请告诉本喵，数组最少能剩下几个数字呢？

比如，a = [1, 6, 1, 1, 4, 4]，我们可以先拿走一个 1 和一个 6，数组就变成 [1, 1, 4, 4]。接着再拿走一个 1 和一个 4，就剩下 [1, 4] 啦。最后再把 1 和 4 也拿走，数组就空空如也，剩下 0 个数字了！是不是很神奇的说？

解题思路喵~

要让最后剩下的元素最少，我们就要尽可能多地进行消除操作，对吧？那什么情况下会让我们停下，不能再消除下去了呢？喵~ 当然是数组里所有剩下的数字都一样的时候啦！因为魔法要求我们必须选两个 不同 的数字才能消除。

所以，这道题的关键就在于那个出现次数最多的数字！它就是我们能不能把所有元素都消掉的“瓶颈”所在。

让我们来分析一下吧！

首先，我们得知道哪个数字最多，以及它出现了多少次。我们可以用一个哈希表（在 C++ 里就是 unordered_map）来统计每个数字的频率。然后找到那个最大的频率，我们叫它 max_freq 好了。

现在，我们可以把数组里的数字分成两拨：

1. 多数派：出现次数最多的那个数字，总共有 max_freq 个。
2. 少数派：除了多数派以外的所有其他数字，总共有 n - max_freq 个。

为了尽可能多地消除，我们的策略当然是优先用“少数派”去和“多数派”配对啦！因为“多数派”是最难被消掉的，我们得用其他所有数字来帮它减少数量。

这样一来，就有两种情况了呐：

情况一：多数派数量太多啦！ (2 * max_freq > n)

这种情况相当于 max_freq > n - max_freq。也就是说，“多数派”的数量比所有“少数派”加起来还要多！ 在这种情况下，每一个“少数派”都可以英勇地和一个“多数派”同归于尽。我们总共可以进行 n - max_freq 次这样的配对。

配对完之后：

• 所有的“少数派”都被消掉了。
• “多数派”也用掉了 n - max_freq 个。
• 还剩下 max_freq - (n - max_freq) 个“多数派”。

把括号拆开，剩下的数量就是 2 * max_freq - n。因为剩下的全都是同一种数字，我们再也没法施展魔法了。所以，这就是最终答案啦！

情况二：多数派数量没那么夸张 (2 * max_freq <= n)

这种情况相当于 max_freq <= n - max_freq。也就是说，“多数派”的数量小于或等于“少数派”的总和。 这可太棒了！这意味着我们有足够的“少数派”去把所有“多数派”都消掉。

当所有“多数派”都被消掉后，剩下的“少数派”们也可以互相消除。只要总数大于1，我们总能找到两个不同的数字配对。

那么最终会剩下多少呢？这就要看总数 n 的奇偶性了。

• 如果 n 是偶数，那么我们总能两两配对，最后全部消完，剩下 0 个。
• 如果 n 是奇数，我们两两配对，最后总会孤零零地剩下一个，剩下 1 个。

所以，在这种情况下，答案就是 n % 2 啦！是不是很简单呢？(＾▽＾)

总结一下我们的策略：

1. 统计所有数字的频率，找到最大频率 max_freq。
2. 判断 2 * max_freq 和 n 的大小关系。
3. 如果 2 * max_freq > n，答案是 2 * max_freq - n。
4. 否则，答案是 n % 2。

代码实现，看本喵的！

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
    // 优化一下输入输出，跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        // 用一个哈希表 (unordered_map) 来统计每个数字出现的次数，超级方便的说！
        unordered_map<int, int> freq;
        int max_freq = 0;

        // 一边读入数字，一边更新频率，同时记录下最大的那个频率 max_freq。
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            freq[a[i]]++;
            // 如果当前数字的频率比已知的最大频率还大，就更新它
            if (freq[a[i]] > max_freq) {
                max_freq = freq[a[i]];
            }
        }

        // 最后，就是我们刚才分析的两种情况啦！
        // 如果最多的那个数字数量的两倍，比总数 n 还大
        if (2 * max_freq > n) {
            // 那么剩下的就是这些无法配对的多数派
            cout << 2 * max_freq - n << '\n';
        } else {
            // 否则，说明我们可以配对掉大部分，最终剩下 0 或 1
            cout << n % 2 << '\n';
        }
    }

    return 0;
}

复杂度分析的说

• 时间复杂度: O(N) 的说。对于每个测试用例，我们只需要遍历一遍数组来统计频率，这花费 O(N) 的时间。哈希表的插入和查找平均是 O(1) 的，所以总时间复杂度就是 O(N) 啦！
• 空间复杂度: O(K) 的说，其中 K 是数组中不同数字的数量。我们用了一个哈希表来存储频率，最坏情况下，如果所有数字都不同（K=N），会需要 O(N) 的空间。

知识点与总结喵~

这道题的核心思想其实就是 贪心，喵~ 我们找到了问题的瓶颈（出现次数最多的元素），然后采取了最直接有效的方式去解决这个瓶颈。

1. 贪心策略 (Greedy Strategy): 解决这类问题的关键是找到正确的贪心角度。这里的贪心选择就是：优先消除掉出现次数最多的那个元素。因为只要它存在，我们就需要消耗其他不同元素来配对，它是我们最大的“麻烦”。
2. 频率统计 (Frequency Counting): unordered_map (哈希表) 或 map 是解决这类计数问题的标准工具，主人要熟练掌握哦！
3. 分类讨论 (Casework): 基于关键变量（这里是 max_freq）与总量的关系进行分类讨论，是简化问题逻辑的常用技巧。

只要抓住了主要矛盾，问题就会迎刃而解啦！主人下次遇到类似的题目，也要试着从这个角度思考哦！加油喵！(๑•̀ㅂ•́)و✧