Moe's CF Life

Appearance

F. Equalize the Array - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 702 (Div. 3) 标签: binary search, data structures, greedy, math, sortings 难度: *1500

题目大意喵~ ​

你好呀，未来的算法大师！今天我们来解决一个很有趣的问题哦~ ฅ'ω'ฅ

Polycarp 有一个数组 a，他想通过移除一些元素，让这个数组变得“美丽”。一个美丽的数组是什么样的呢？就是存在一个数字 C，数组里剩下的每一种数字，要么不出现（0次），要么就恰好出现 C 次。

我们的任务就是，计算出最少需要移除多少个元素，才能让数组 a 变得美丽。

举个栗子，a = [1, 3, 2, 1, 4, 2]。

  • 数字 1 出现了 2 次。
  • 数字 2 出现了 2 次。
  • 数字 3 出现了 1 次。
  • 数字 4 出现了 1 次。

如果我们选择目标次数 C = 2，那么数字 1 和 2 就不用动啦。但是数字 3 和 4 只出现了 1 次，不符合 C=2 的要求，所以我们必须把它们全部移除。总共需要移除 2 个元素。最后数组就可能变成 [1, 2, 1, 2]，这就很美丽了喵~

我们的目标就是找到那个最优的 C，使得总移除数最小！

解题思路喵~ ​

喵~ 这个问题看起来有点复杂，但别担心，我们一步步来分析，很快就能找到思路的！

第一步：关注频率，而不是数值 ​

首先我们注意到，数组里具体的数值是多少（比如是1还是100）并不重要，重要的是每个数值出现了多少次，也就是它们的频率。所以，第一步当然是统计一下数组里每个数字的出现次数啦。我们可以用一个 map 来轻松完成这件事，map<int, int> counts，键是数字，值是它出现的次数。

第二步：关注频率的频率 ​

现在我们有了一堆数字和它们各自的频率。比如 a = [1, 2, 3, 3, 3, 2, 6, 6]，统计后得到：

  • 1 出现了 1 次
  • 2 出现了 2 次
  • 3 出现了 3 次
  • 6 出现了 2 次

我们发现，数字 2 和 6 的行为模式是一样的，它们都出现了 2 次。所以，我们可以把问题再简化一下：不关心是哪个数字了，只关心有多少种数字出现了 k 次。

我们再用一个 map，map<int, int> freq_counts，来统计频率的频率。 对于上面的例子：

  • 出现 1 次的数字有 1 种 (就是数字 1)。
  • 出现 2 次的数字有 2 种 (数字 2 和 6)。
  • 出现 3 次的数字有 1 种 (就是数字 3)。 所以 freq_counts 就是 {1: 1, 2: 2, 3: 1}。

第三步：选择最优的目标次数 C ​

我们的核心任务是选择一个目标次数 C，使得移除的元素最少。一个非常重要的贪心思路是：最优的 C 一定是已经存在的某个频率。为什么呢？因为如果我们选择一个不存在的频率作为 C，我们可以微调它直到它等于某个已存在的频率，而总移除数不会增加。所以，我们只需要遍历所有在 freq_counts 中出现过的频率，把它们作为 C 的候选者，然后计算每种情况下的移除数，取最小值就好啦！

第四步：高效计算移除数 ​

假设我们选定了候选目标 C。现在怎么计算总移除数呢？ 对于原来出现 f 次的某个数字：

  1. 如果 f < C，我们没办法通过移除元素让它的次数增加到 C。所以，只能把这 f 个元素全部移除掉。
  2. 如果 f >= C，为了让它的次数变成 C，我们需要移除 f - C 个元素。

所以，对于一个给定的 C，总移除数 = (所有频率 f < C 的数字的移除数总和) + (所有频率 f >= C 的数字的移除数总和)。

  • 对于 f < C 的部分：假设有 count_f 种数字都出现了 f 次，那么这部分需要移除 f * count_f 个元素。总和就是 sum(f * count_f) for all f < C。
  • 对于 f >= C 的部分：假设有 count_f 种数字都出现了 f 次，那么这部分需要移除 (f - C) * count_f 个元素。总和就是 sum((f - C) * count_f) for all f >= C。

如果我们对每个候选 C 都重新遍历一次所有频率来计算这个总和，效率太低了，可能会超时哦。这里就需要一个优化技巧！

第五步：前缀和/后缀和优化！ ​

我们可以把 freq_counts 里的 (频率, 种类数) 对取出来，按频率从小到大排序。然后我们遍历这个排好序的列表，依次将每个频率作为候选 C。

在遍历过程中，我们可以维护几个变量来O(1)地计算移除数：

  • left_sum_prod: 表示我们已经处理过的、所有频率小于当前 C 的那些数字，它们需要被全部移除。这个变量累加 f * count_f 的值。
  • right_sum_prod: 表示还没处理的、所有频率大于或等于当前 C 的那些数字的总元素个数。初始值是数组总元素个数 n。
  • right_sum_count: 表示还没处理的、所有频率大于或等于当前 C 的那些数字的种类数。初始值是原数组中不同数字的总数。

当我们考察一个候选 C 时：

  • 来自 f < C 的移除数：就是 left_sum_prod。
  • 来自 f >= C 的移除数：这部分的总移除数是 sum((f - C) * count_f)，可以变形为 sum(f * count_f) - C * sum(count_f)。这正好就是 right_sum_prod - C * right_sum_count！

所以，对于每个候选 C，总移除数就是 left_sum_prod + (right_sum_prod - C * right_sum_count)。

计算完当前 C 之后，我们就需要更新这几个变量，为计算下一个 C 做准备。具体来说，就是把当前 C 的贡献从 "right"（右边/未处理）移动到 "left"（左边/已处理）。

这样，我们只需要一次遍历就可以计算出所有候选 C 对应的移除数，然后找到最小值！是不是很巧妙呀？喵~

代码实现喵！ ​

cpp
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    // 第一步：统计每个数字出现的次数
    std::map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        counts[x]++;
    }

    if (n == 0) {
        std::cout << 0 << "\n";
        return;
    }

    // 第二步：统计频率的频率
    // freq_counts 的键是频率，值是拥有该频率的数字有多少种
    std::map<int, int> freq_counts;
    for (auto const& [num, freq] : counts) {
        freq_counts[freq]++;
    }

    // 将 (频率, 种类数) 对放入 vector 中。
    // 因为 std::map 的迭代器是按键排序的，所以 fcv 天然按频率从小到大排序。
    std::vector<std::pair<int, int>> fcv;
    for (auto const& [freq, count] : freq_counts) {
        fcv.push_back({freq, count});
    }

    long long min_removals = n; // 最坏情况是移除所有元素

    // 第五步的优化变量
    long long left_sum_prod = 0; // f < C 的部分，总移除数
    long long right_sum_prod = 0; // f >= C 的部分，元素总数
    
    // 初始化 right_sum_prod，初始时所有元素都在 "右边"
    for (const auto& p : fcv) {
        right_sum_prod += (long long)p.first * p.second;
    }
    
    // f >= C 的部分，不同数字的种类数
    long long right_sum_count = counts.size();

    // 第三步：遍历所有可能的 C
    for (const auto& p : fcv) {
        long long C = p.first; // 当前候选的目标频率
        long long count_at_C = p.second; // 有多少种数字的频率是 C

        // 第四步：计算当前 C 的总移除数
        // 1. 对于频率 f < C 的数字，必须全部移除。移除成本就是 left_sum_prod
        long long removals_from_smaller_freqs = left_sum_prod;
        
        // 2. 对于频率 f >= C 的数字，每个需要移除 f - C 个。
        // 总移除数 = sum((f-C)*count_f) = sum(f*count_f) - C*sum(count_f)
        // 这就是 right_sum_prod - C * right_sum_count
        long long removals_from_larger_equal_freqs = right_sum_prod - C * right_sum_count;
        
        long long current_removals = removals_from_smaller_freqs + removals_from_larger_equal_freqs;
        
        min_removals = std::min(min_removals, current_removals);

        // 为下一个 C 更新变量，将当前 C 的贡献从 "右边" 移到 "左边"
        left_sum_prod += C * count_at_C;
        right_sum_prod -= C * count_at_C;
        right_sum_count -= count_at_C;
    }

    std::cout << min_removals << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(N log N) 的说。

    • 遍历输入数组并用 std::map 统计 counts，这里因为最多有 N 个不同的数，所以是 O(N log N)。
    • 遍历 counts 来构建 freq_counts，设不同数字的数量为 U (U <= N)，这一步是 O(U log U_freq)，其中 U_freq 是不同频率的数量。
    • 最后遍历 fcv 的循环，次数为 U_freq。
    • 整个过程的瓶颈在于第一步用 map 统计 counts，所以总体时间复杂度是 O(N log N)。如果用 std::unordered_map，平均时间复杂度可以优化到 O(N)。

  • 空间复杂度: O(U) 的说，其中 U 是数组中不同元素的数量。

    • 我们需要 counts 这个 map 来存储 U 个不同数字的频率，最坏情况下 U 可以等于 N。
    • freq_counts 和 fcv 的大小不会超过 U。
    • 所以空间复杂度是 O(U)，最坏情况是 O(N)。

知识点与总结 ​

这次的冒险旅程让我们学会了好多东西呢，喵~

  1. 频率分析: 这是一个非常强大的武器！当题目中元素的具体值不重要，而它们的数量和分布更重要时，首先想到的就应该是频率分析。
  2. 问题转化: 我们把一个关于数组元素的问题，转化为了一个关于“频率”的问题，接着又转化为了一个关于“频率的频率”的问题。这种层层抽象和简化的思想在算法题中非常关键。
  3. 贪心选择: 猜想并相信最优解一定存在于某个特定的、有限的候选集合中（这里是已存在的频率），是解决很多优化问题的关键一步。
  4. 前缀/后缀和思想: 这是优化循环计算的经典技巧！通过维护几个动态变化的和（running sums），我们把每次 O(N) 的计算量降低到了 O(1)，从而让整个算法的效率大大提升。

希望这篇题解能帮到你！继续加油，你超棒的！喵~ (ฅ^•ﻌ•^ฅ)

Released under the MIT License.

Copyright © 2024-present Moe