D. Candy Box (easy version) - 题解

比赛与标签

比赛: Codeforces Round 570 (Div. 3) 标签: greedy, sortings 难度: *1400

题目大意喵~

各位主人，下午好喵~ ฅ(๑•́ ▽ •̀๑)

这道题是说，我们有一个装满糖果的盒子，里面有 n 颗糖，糖果有不同的种类 a_i。我们的任务呢，就是从这些糖果里挑选一些出来，打包成一份礼物！

不过，有一个非常重要的规则哦：礼物中，每种糖果的数量必须是独一无二的。比如说，你可以拿2颗A类糖和1颗B类糖，这是合法的喵~ 但是，你不可以拿2颗A类糖和2颗B类糖，因为数量 "2" 重复了，这样就不行啦！

我们的目标，就是要让这份礼物的总糖果数尽可能地多！请问最多能装多少颗糖呢？我们要回答 q 次独立的询问哦。

解题思路喵~

这道题的目标是让总糖果数最大，一看到“最大”、“最优”这样的字眼，我们聪明的猫娘脑海里就应该闪过“贪心”两个字啦！( •̀ ω •́ )✧

怎么个贪心法呢？为了让总数最大，我们肯定希望每次拿的糖果数量都尽可能多，对吧？

举个栗子：如果我们有3种糖果，它们的数量分别是 [5, 5, 5]。

我们先看数量最多的那种糖（其实这里都一样多啦），有5颗。为了总数最大，我们当然想拿5颗！好，我们决定拿5颗A类糖。现在我们用掉了一个数量：5。
接着我们看B类糖，它也有5颗。但是我们已经用过 5 这个数量了，所以不能再拿5颗了。为了尽可能多拿，我们退而求其次，拿 5-1=4 颗好了！现在我们用掉的数量有：5, 4。
最后看C类糖，它也有5颗。我们已经用过 5 和 4 了，所以这次最多只能拿 4-1=3 颗。这样，我们总共能拿 5 + 4 + 3 = 12 颗糖，这就是最优解啦！

从这个栗子中，我们可以总结出贪心策略：

统计数量：首先，我们数一数盒子里每种糖果各有多少颗。我们把这些数量（频率）记录下来。
贪心选择：我们应该优先满足那些数量多的糖果种类，让它们在礼物中贡献尽可能大的数量。
- 把所有糖果种类的数量（频率）从大到小排序。
- 对于数量最多的那个种类，我们直接取它全部的数量 f_1。
- 对于数量第二多的种类，我们想取一个比 f_1 小、且尽可能大的数量。最好的选择自然是 f_1 - 1。当然，我们也要确保我们有这么多糖，所以实际能取的是 min(拥有的数量, f_1 - 1)。
- 以此类推，每次我们选择一个新的糖果种类时，都尝试取一个比上一次所取数量小 1 的糖果数。

这个排序再处理的思路是可行的，但时间复杂度会是 O(N log N)。我们可以做得更好喵！

更高效的贪心实现 O(N)

让我们看看AC代码里的绝妙思路，它不需要排序，超级快！

第一步：统计频率。和上面的方法一样，我们先用一个 freq 数组统计每种糖果（type 1 到 n）出现的次数。
第二步：统计频率的频率！这一步是关键喵~ 我们再用一个数组 count_of_counts，其中 count_of_counts[k] 表示“出现次数恰好为 k 的糖果种类有多少个”。
- 比如，我们有2种糖果出现了4次，3种糖果出现了2次，那么 count_of_counts[4] = 2，count_of_counts[2] = 3。
第三步：从大到小贪心。我们从最大的可能数量 c = n 开始，一直遍历到 1。
- 我们维护一个 available_types 变量，可以理解为“当前可供选择的糖果种类”的“蓄水池”。
- 当遍历到数量 c 时，我们就把所有频率恰好为 c 的糖果种类全部加入到“蓄水池”里 (available_types += count_of_counts[c])。
- 然后，检查“蓄水池”里有没有可用的糖果种类 (available_types > 0)。如果有，太棒了！我们就可以组成一个包含 c 颗糖的包裹！
- 我们把 c 加入总数 total_candies，并从“蓄水池”中消耗掉一个名额 (available_types--)。

这个方法为什么是对的呢？因为我们从大到小遍历 c，所以总是优先尝试组成数量最大的包裹。而“蓄水池” available_types 里装的，是所有频率大于等于当前 c 的、尚未被使用的糖果种类。如果一个种类的糖果有 k 颗 (k > c)，它在第 k 轮被加入蓄水池，如果在第 k 轮没被用掉，它依然可以留到第 c 轮来组成一个数量为 c 的包裹。这个过程完美地模拟了我们的贪心策略，而且超级高效！

代码实现喵！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    
    // 步骤1：统计每种糖果的数量（频率），喵~
    // freq[i] 表示种类为 i 的糖果有多少颗。
    std::vector<int> freq(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        freq[a]++;
    }

    // 步骤2：统计频率的频率，这是最关键的一步哦！
    // count_of_counts[k] 表示“拥有 k 颗糖果”的种类有多少个。
    std::vector<int> count_of_counts(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        if (freq[i] > 0) {
            count_of_counts[freq[i]]++;
        }
    }

    long long total_candies = 0;
    int available_types = 0; // 我们的“蓄水池”，存放可用的糖果种类数量

    // 步骤3：从大到小贪心选择！
    // c 代表我们希望在礼物中包含的糖果数量
    for (int c = n; c >= 1; --c) {
        // 把所有频率恰好为 c 的糖果种类，加入到我们的蓄水池中
        available_types += count_of_counts[c];
        
        // 如果蓄水池不为空，说明我们有糖果种类可以满足数量 c 的要求
        if (available_types > 0) {
            // 太棒了！我们成功拿到了 c 颗糖！
            total_candies += c;
            // 用掉了一个糖果种类名额，从蓄水池里拿走一个
            available_types--;
        }
    }
    
    std::cout << total_candies << "\n";
}

int main() {
    // 加上这两行可以让输入输出快如闪电，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int q;
    std::cin >> q;
    while (q--) {
        solve();
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(n) 的说。对于每个查询，我们有三个循环。第一个循环读取n个糖果并统计频率，是 O(n)。第二个循环遍历频率数组，也是 O(n)。第三个贪心循环从 n 到 1，还是 O(n)。所以总的时间复杂度是 O(n)，非常高效！因为所有查询的n加起来不超过 2*10^5，所以总时间也是线性的，完全没问题呐。
空间复杂度: O(n) 的说。我们需要一个 freq 数组和一个 count_of_counts 数组，它们的大小都和 n 相关，所以空间复杂度是 O(n)。

知识点与总结喵~

这道题真是太有趣啦，让我们来总结一下学到了什么吧！

贪心大法好：遇到求解最优值（最大/最小）的问题，一定要先想想贪心策略！本题的核心就是“为了总和最大，每次都取当前能取的最大值”。
频率的频率 (Frequency of Frequencies)：这是一个非常巧妙的技巧！当处理与计数和频率相关的贪心问题时，如果直接排序会导致复杂度过高，可以尝试统计频率的频率，把问题转化为线性扫描，从而优化时间复杂度。这是一种类似计数排序的思想，非常实用！
逆向思维: 从大到小遍历（c从n到1）是解决这类贪心问题的常用模式。正向从小到大思考可能会很复杂，但逆向思考，优先满足最大的需求，往往能让问题变得简单清晰。

希望这篇题解能帮助到各位主人！如果还有不懂的地方，随时可以再来问我哦~ 一起加油，攻克更多有趣的题目吧！喵~ (´,,•ω•,,)♡

D. Candy Box (easy version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

更高效的贪心实现 O(N) ​

代码实现喵！ ​

复杂度分析的说 ​

知识点与总结喵~ ​