N. Waste Sorting - 题解

比赛与标签

比赛: 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules) 标签: greedy, implementation 难度: *900

题目大意喵~

主人你好呀~ 这是一道关于垃圾分类的可爱问题，喵！

我们有三个垃圾桶，它们的容量分别是 c1, c2, c3。

1号桶只能装纸类垃圾。
2号桶只能装塑料垃圾。
3号桶可以装其他所有类型的垃圾。

现在我们有五堆垃圾要处理：

a1 份纯纸类垃圾，必须扔进1号桶。
a2 份纯塑料垃圾，必须扔进2号桶。
a3 份纯其他垃圾，必须扔进3号桶。
a4 份部分纸类垃圾，可以扔进1号桶，也可以扔进3号桶。
a5 份部分塑料垃圾，可以扔进2号桶，也可以扔进3号桶。

我们的任务是判断，是否存在一种方案，能把所有垃圾都成功地扔进对应的垃圾桶里，并且不超过每个桶的容量限制。如果可以，就输出 "YES"，否则输出 "NO"，很简单对吧~

解题思路分析喵！

这道题看起来有点复杂，因为有两种垃圾（a4 和 a5）的去向是不确定的。但是只要我们理清思路，就会发现它其实是一道非常直观的贪心问题呐！

第一步：处理没有选择的垃圾

首先，我们先把那些“死规定”的垃圾放进去。a1 必须去1号桶，a2 必须去2号桶，a3 必须去3号桶。这是没有任何商量余地的。

所以，我们先更新一下各个桶的剩余容量：

1号桶剩余容量：c1 = c1 - a1
2号桶剩余容量：c2 = c2 - a2
3号桶剩余容量：c3 = c3 - a3

如果在这一步之后，任何一个桶的剩余容量变成了负数，那就说明连最基本的垃圾都装不下了，后续的分配也就无从谈起。所以直接判断为 "NO" 就可以啦，喵~

第二步：贪心处理灵活的垃圾

现在，我们来处理 a4 和 a5 这两种可以灵活放置的垃圾。

a4 可以去 1号桶或 3号桶。
a5 可以去 2号桶或 3号桶。

注意到一个关键点没有？3号桶像是一个“万能”的备用桶，既可以接收 a4 的“溢出”，也可以接收 a5 的“溢出”。而1号桶和2号桶是“专属”的。

为了让成功的可能性最大化，我们应该采取什么样的策略呢？当然是优先使用专属的垃圾桶啦！

这就像坐车一样，1号桶是“纸类专车”，2号桶是“塑料专车”，而3号桶是“万能公交车”。为了不让公交车过分拥挤，我们应该让能坐专车的垃圾尽量坐专车！

所以我们的贪心策略是：

对于 a4 份垃圾，我们尽最大努力把它们塞进1号桶。1号桶最多还能装 c1 个，所以我们最多可以放 min(a4, c1) 个 a4 垃圾进去。
如果 a4 还有剩下的（也就是 a4 > c1 的情况），那么这些剩下的 a4 - c1 个垃圾就别无选择，必须全部扔进3号桶。
同理，对于 a5 份垃圾，我们尽最大努力把它们塞进2号桶。最多可以放 min(a5, c2) 个。
如果 a5 还有剩下的，这些 a5 - c2 个垃圾也必须全部扔进3号桶。

第三步：最终检查

经过上面的贪心分配后，所有 a4 和 a5 的垃圾都有了归宿。那些从1号桶和2号桶“溢出”的垃圾，是我们强制要塞进3号桶的。

我们只需要计算一下，总共有多少垃圾被强制塞进了3号桶，然后看看3号桶的剩余容量 c3 够不够装。

从 a4 溢出到3号桶的数量是 max(0, a4 - c1)。
从 a5 溢出到3号桶的数量是 max(0, a5 - c2)。

只要 c3 >= max(0, a4 - c1) + max(0, a5 - c2)，就说明所有垃圾都能装下，答案就是 "YES"！否则就是 "NO"。

这个思路是不是很清晰呀？喵~

代码实现の说

cpp

#include <iostream>
#include <algorithm>

// Function to solve a single test case
void solve() {
    long long c1, c2, c3;
    std::cin >> c1 >> c2 >> c3;
    long long a1, a2, a3, a4, a5;
    std::cin >> a1 >> a2 >> a3 >> a4 >> a5;

    // 第一步：先把 a1, a2, a3 这些没有选择的垃圾放进去喵~
    // 然后更新垃圾桶的剩余容量
    c1 -= a1;
    c2 -= a2;
    c3 -= a3;

    // 如果在放完必须放的垃圾后，有任何一个桶的容量小于0，那肯定是不行的啦
    if (c1 < 0 || c2 < 0 || c3 < 0) {
        std::cout << "NO\n";
        return;
    }

    // 第二步：贪心处理可以灵活放置的垃圾 (a4 和 a5)
    // 我们的策略是优先填满专属垃圾桶（1号和2号），以减轻通用垃圾桶（3号）的压力

    // 对于 a4 (部分纸类)，它们可以去1号或3号桶。
    // 我们计算一下，如果优先填1号桶，会有多少 a4 垃圾因为1号桶满了而必须“溢出”到3号桶。
    // std::max(0LL, ...) 是为了防止 a4 - c1 得到负数，如果 c1 足够大，溢出量就是0。
    long long a4_overflow = std::max(0LL, a4 - c1);

    // 对于 a5 (部分塑料)，同理，计算溢出到3号桶的数量。
    long long a5_overflow = std::max(0LL, a5 - c2);

    // 第三步：最终检查！
    // 把所有必须放入3号桶的溢出垃圾加起来。
    long long total_overflow = a4_overflow + a5_overflow;

    // 看看3号桶的剩余容量是否能容纳下这些全部的溢出垃圾。
    if (c3 >= total_overflow) {
        std::cout << "YES\n"; // 足够装，太棒了喵！
    } else {
        std::cout << "NO\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(1) 的说对于每一个测试用例，我们只进行了一系列的减法、比较和求最大值的操作。这些操作的次数是固定的，与输入数值的大小无关，所以时间复杂度是常数级别的，超级快的说！
空间复杂度: O(1) 的说我们只使用了几个 long long 类型的变量来存储输入的容量和垃圾数量，没有使用额外的数组或者其他数据结构。所以占用的空间也是常数级别的呐。

知识点与总结

这道题虽然标签是 *900，但它是一个非常经典的贪心算法入门题，很适合用来理解贪心的思想喵~

贪心策略的核心: 当面临多种选择时，总是做出在当前状态下看起来最优的决策。在这道题里，“最优”的决策就是优先利用专属资源（1号和2号桶），把宝贵的、通用的资源（3号桶）留到万不得已的时候再用。
问题分解: 解决问题的好习惯是先处理确定的部分，再处理不确定的部分。我们先放置 a1, a2, a3，简化了问题，然后再集中精力思考 a4, a5 的分配策略。
编程技巧: 在计算溢出量时，使用 std::max(0LL, a4 - c1) 是一个很棒的小技巧。它既能正确处理 a4 > c1 的情况，也能在 a4 <= c1 时优雅地得到0，避免了写 if-else 判断，让代码更简洁健壮！

希望这篇题解能帮到你哦，主人！下次遇到类似的问题，也要像这样一步步分析，找到最优的策略，加油喵~！

N. Waste Sorting - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路分析喵！ ​

代码实现の说 ​

复杂度分析 ​

知识点与总结 ​