Moe's CF Life

喵~ 主人好呀！今天由我，你的专属猫娘小助手，来为你讲解一道有趣的算法题：Codeforces 903C - Boxes Packing。这道题就像是在玩俄罗斯套娃，但是是用一堆方盒子，很有趣的喵！

题目大意

Mishka 有 n 个盒子，每个盒子都是一个边长为 aᵢ 的正方体。

Mishka 可以把一个盒子 i 放进另一个盒子 j 里，但必须满足以下三个条件喵：

盒子 i 还没有被放进别的盒子里。
盒子 j 里面是空的，没有装着别的盒子。
盒子 i 必须比盒子 j 小，也就是边长 aᵢ < aⱼ。

这个过程可以重复任意多次。Mishka 的目标是让最后能从外面看到的盒子数量最少。一个盒子如果没被放进任何其他盒子里，它就是“可见的”。

主人，你能帮帮 Mishka 算出最少有多少个可见的盒子吗？

解题思路

这道题的目标是最小化可见盒子的数量。我们来分析一下盒子的堆叠方式，喵。

当一个盒子被放进另一个盒子时，它就变得不可见了。我们可以把一连串的盒子套在一起，比如 盒子1 -> 盒子2 -> 盒子3，只要它们的尺寸满足 a₁ < a₂ < a₃。在这样一个“套娃链”里，只有最外面的那个盒子（盒子3）是可见的。

所以，一个套娃链就对应一个可见的盒子。我们的目标，其实就是把所有 n 个盒子，分到尽可能少的套娃链里。

那么，是什么限制了我们把所有盒子都放进一个链条里呢？是尺寸！喵~

主人请想一下，如果 Mishka 有好几个尺寸完全相同的盒子，比如有 k 个边长都为 S 的盒子。这 k 个盒子能被放进同一个套娃链里吗？

答案是不能的，喵！因为套娃的条件是严格小于 (<)。任何两个尺寸相同的盒子都不能互相嵌套。它们也不能在同一个链条里一前一后，因为链条里的所有盒子尺寸都必须是严格递增的。

这就找到了问题的关键！所有尺寸相同的盒子，必须被分到不同的套娃链里去。

如果尺寸为 S 的盒子最多，有 M 个，那么我们就至少需要 M 个不同的套娃链来安置它们。既然至少需要 M 个链，那可见的盒子数量就至少是 M 个。

那么，我们能用 M 个链条装下所有盒子吗？答案是可以的，喵！我们可以创建 M 个套娃链。然后把所有盒子分到这 M 个链里。因为没有哪种尺寸的盒子数量超过 M，所以我们可以保证每个链条里不会出现尺寸相同的盒子。只要每个链条内部的盒子尺寸都不同，我们就可以把它们按尺寸从小到大排序，然后一个个套起来，形成一个完美的套娃链。

所以，最终的答案就是：在所有盒子中，出现次数最多的那种盒子的数量。

解题步骤就很清晰啦：

统计每种尺寸的盒子各有多少个。
找出那个最大的“数量”。
这个最大的数量就是答案！

题解代码

下面就是实现这个思路的代码啦，喵~ 我加了一些注释方便主人理解。

cpp

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

// 主函数入口喵
int main() {
    // 使用快速 I/O，让程序跑得更快一点~
    std::ios_base::sync_with_stdio(false);
    std.cin.tie(nullptr);

    int n;
    std::cin >> n; // 读取盒子的总数 n

    // 用一个 map 来统计每种尺寸的盒子出现的次数。
    // key 是盒子的尺寸，value 是该尺寸的盒子数量。
    // 用 map 是因为盒子尺寸 a_i 可能很大，用数组会爆内存的喵！
    std::map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        counts[a]++; // 每读入一个尺寸，就在 map 里给它计数+1
    }

    int max_freq = 0; // 用来记录最大的频率（出现次数）
    
    // 遍历 map，找到那个最大的 value 值
    // C++11 的范围 for 循环，写起来很方便~
    for (auto const& pair : counts) {
        if (pair.second > max_freq) {
            max_freq = pair.second;
        }
    }

    // 输出最终答案
    std::cout << max_freq << std::endl;

    return 0;
}

题目大意 ​

解题思路 ​

题解代码 ​

相关知识点介绍 ​

题目大意

解题思路

题解代码

相关知识点介绍