C. Hard Problem - 题解

比赛与标签

比赛: Codeforces Round 993 (Div. 4) 标签: greedy, math 难度: *800

问题是什么喵？

喵哈~！各位同学，今天我们来解决一个名字听起来很“硬核”，但其实超级有趣的问题呐！

想象一下，我们有一个大教室，里面有两排座位，每一排都有 m 个座位。现在，有三群可爱的小猴子要来上课啦：

有 a 只小猴子非常固执，它们只想坐在第1排。
有 b 只小猴子也很固执，它们只想坐在第2排。
还有 c 只小猴子特别随和，它们哪一排都可以坐。

我们的任务就是，作为聪明的Ball老师，要尽可能多地给这些可爱的小猴子们安排座位！要怎么做才能让最多的小猴子坐下呢？

猫娘的贪心小妙招~

这个问题看起来有点让人头大，但其实只要抓住关键点，就变得很简单了喵~ 这就是典型的贪心思想哦！

贪心的核心就是，每次都做出当前看起来最优的选择。对于安排座位来说，谁的需求最“挑剔”，我们就应该最先满足谁，对不对？如果连最挑剔的猴子都安排不明白，那它们就肯定没法坐下了。

所以，我们的策略分为三步走：

第一步：优先安排“挑剔”的猴子！ 有 a 只小猴子非第1排不坐，有 b 只小猴子非第2排不坐。它们的选择最少，所以我们必须先给它们安排座位，不然它们就没地方坐啦！

对于第1排，有 m 个座位，但有 a 只猴子想坐。所以，我们最多能安排 min(a, m) 只猴子坐下。如果猴子比座位多，就坐满；如果座位比猴子多，就全坐下。
同理，对于第2排，我们最多能安排 min(b, m) 只猴子坐下。

第二步：再安排“随和”的猴子！ 安排完这些“挑剔”的猴子之后，我们来看看两排还剩下多少空位。

第1排剩下的空位是：m - min(a, m)
第2排剩下的空位是：m - min(b, m)
所以，总共剩下的空位就是 (m - min(a, m)) + (m - min(b, m))。

现在轮到 c 只“随和”的猴子登场了！它们可以在任何剩下的空位上坐下。所以，它们能坐下的数量就是它们自身的数量 c 和总剩余座位数的较小值，也就是 min(c, total_remaining_seats)。

第三步：汇总结果！ 最后，把三部分成功坐下的猴子数量加起来，就是我们能安排的最多猴子数量啦！ 总数 = (第1排坐下的猴子) + (第2排坐下的猴子) + (随和猴子坐下的数量)

是不是很简单喵？只要一步一步来，问题就迎刃而解了！

代码魔法时间！

cpp

#include <iostream>
#include <algorithm>

void solve() {
    long long m, a, b, c;
    std::cin >> m >> a >> b >> c;

    // 第一步：优先满足有固定偏好的猴子们，因为它们没得选呀！
    // 想要坐第1排的猴子，能坐下的数量取决于猴子数量a和座位数m的最小值。
    long long seated_row1_pref = std::min(a, m);
    // 同理，对于只想坐第2排的猴子们也是一样。
    long long seated_row2_pref = std::min(b, m);

    // 第二步：安排好它们之后，我们来计算一下两排还剩下多少空座位。
    long long remaining_seats_row1 = m - seated_row1_pref;
    long long remaining_seats_row2 = m - seated_row2_pref;
    long long total_remaining_seats = remaining_seats_row1 + remaining_seats_row2;

    // 第三步：那些没有偏好的“随和”猴子们，就可以坐进这些剩下的任何一个空位里。
    // 它们能坐下的数量，取决于它们的总数c和总剩余座位数的最小值。
    long long seated_no_pref = std::min(c, total_remaining_seats);

    // 最后，把所有成功坐下的猴子数量加起来，就是最终答案啦！喵~
    long long total_seated = seated_row1_pref + seated_row2_pref + seated_no_pref;

    std::cout << total_seated << std::endl;
}

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) 的说！对于每个测试用例，我们只进行了一系列的加、减和求最小值操作。这些都是常数时间的操作，和输入 m, a, b, c 的具体数值大小无关，所以超级快！
空间复杂度: O(1) 的说！我们只用了几个变量来存储输入和中间计算结果，没有使用随输入规模增大的额外数据结构。所以空间复杂度也是恒定的，非常节省内存呢！

猫娘的小课堂时间

这道题虽然名字叫"Hard Problem"，但其实是个温柔的陷阱啦，主要考验的是大家能不能看透问题的本质。

核心思想：贪心算法 (Greedy Algorithm) 这道题最核心的知识点就是贪心啦！贪心算法的关键在于，通过一系列局部最优解，最终得到全局最优解。在这里，我们的局部最优策略就是“优先满足限制最强的需求”，这个策略被证明是正确的，因为不这样做的话，那些有严格偏好的猴子可能会因为座位被无偏好的猴子占据而无法入座，导致总数变少。
解题步骤分解 面对一个问题，学会把它分解成几个小步骤是很重要的能力哦。我们先把问题分成“处理偏好猴子”和“处理无偏好猴子”两步，是不是就清晰多啦？先处理约束强的，再处理约束弱的，是解决这类问题的一个通用思路。
边界条件与min函数 不要忘记考虑各种限制条件！比如猴子的数量可能比座位多，也可能比座位少。使用 std::min 函数可以很方便地处理这种“不能超过容量”的情况，是C++编程中非常实用的小技巧喵~

希望大家通过这道题，对贪心思想有更深的理解！继续加油哦，喵~！

C. Hard Problem - 题解 ​

比赛与标签 ​

问题是什么喵？ ​

猫娘的贪心小妙招~ ​

代码魔法时间！ ​

时空复杂度分析喵 ​

猫娘的小课堂时间 ​