J. Waiting for... - 题解

比赛与标签

比赛: 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) 标签: greedy, implementation 难度: *800

喵喵，题目在说什么呀？

这道题呀，是在模拟一个叫 Monocarp 的小可怜在公交站等车的故事，呐。

事情是这样滴：

会有一系列按时间顺序发生的事件。
事件有两种：
- P p: 表示车站来了 p 个新乘客。
- B b: 表示来了一辆有 b 个空座位的公交车。
当公交车来了之后，除了 Monocarp 以外的所有人都会尝试上车。
- 如果座位比等车的人多（或一样多），那大家就都开开心心地上去啦。
- 如果座位不够，那就只能按座位数上那么多人，剩下的人继续等下一班。
在其他所有人都上完车之后，如果车上至少还剩一个空位，那么 Monocarp 就可以选择上这辆车。

我们的任务就是，对于每一辆到站的公交车，判断一下 Monocarp 有没有可能上车，然后输出 "YES" 或者 "NO" 就可以啦，喵~

本喵的思考时间！

这道题其实超级直白的，就像是跟着故事一步步走下去一样，我们把它叫做模拟，的说！我们只需要一个变量来记录当前车站有多少人（当然，不包括 Monocarp 啦），然后按照事件顺序来更新这个人数就好了。

让本喵来带你一步步分析吧：

首先，我们需要一个变量，就叫 current_people 吧，来记录在车站等车的乘客数量。一开始，车站空无一人，所以 current_people = 0。
接下来，我们一个一个地处理事件：
- 如果来的是乘客 (P p)：这很简单嘛，车站的人数增加了 p 个。所以我们直接 current_people += p 就行啦。
- 如果来的是公交车 (B b)：这是最关键的一步哦，要仔细听呐！
  - Monocarp 能不能上车，取决于什么呢？取决于其他 current_people 个人上车后，车上还有没有空位给他。
  - 也就是说，公交车的座位数 b 必须严格大于等车的人数 current_people。为什么是严格大于呢？因为如果 b 恰好等于 current_people，那么座位就刚好被占满了，没有多余的给 Monocarp 了呀！
  - 所以，判断条件就是：if (b > current_people)。
  - 如果这个条件成立，说明 Monocarp 有位置！我们就输出 "YES"。之后，所有 current_people 个人都上车了，车站又变空了，所以我们把 current_people 重置为 0。
  - 如果条件不成立 (b <= current_people)，说明 Monocarp 没机会上车，太惨了喵~ 我们就输出 "NO"。然后，这辆车会带走 b 个人，所以车站里等车的人数会减少 b 个，我们更新 current_people -= b。

就这样循环处理完所有事件，问题就解决啦！是不是很简单呢？这其实也是一种贪心思想，因为我们每次只根据当前的情况做出了最优决策，而不需要考虑未来的事件，喵~

代码魔法，变！

下面就是能通过这道题的魔法代码啦！本喵已经加上了详细的注释，让你看得更明白~

cpp

#include <iostream>
#include <string>

using namespace std;

int main() {
    // n 是事件的总数，喵~
    int n;
    cin >> n;

    // 用一个 long long 类型的变量来记录当前等车的人数（不包括Monocarp）
    // 用 long long 是个好习惯，防止人太多 int 存不下，虽然这题 int 也够啦
    long long current_people = 0;

    // 循环处理 n 个事件
    for (int i = 0; i < n; i++) {
        string event;
        cin >> event; // 读取事件类型是 'P' 还是 'B'

        if (event == "P") {
            // 如果是 'P' 事件，说明有人来了
            long long num;
            cin >> num; // 读取来了多少人
            current_people += num; // 更新等车人数
        } else if (event == "B") {
            // 如果是 'B' 事件，说明公交车来了
            long long seats;
            cin >> seats; // 读取车上有多少座位

            // 核心判断逻辑！座位数是否严格大于等车人数？
            if (seats > current_people) {
                // 如果座位 > 人数，太棒了！Monocarp有位置！
                cout << "YES" << endl;
                // 其他人都上车了，车站清空
                current_people = 0;
            } else {
                // 如果座位 <= 人数，呜呜，Monocarp上不去
                cout << "NO" << endl;
                // 车上去了 seats 个人，更新等车人数
                current_people -= seats;
            }
        }
    }

    return 0; // 程序结束，喵~
}

效率分析喵~

时间复杂度: O(n) 的说。我们只需要一个循环遍历所有的 n 个事件，循环体内部的操作都是常数时间的（加减法、比较、输入输出），所以总的时间和事件数量 n 成正比。
空间复杂度: O(1) 的说。我们只用了几个变量（n, current_people, event, num, seats）来存储信息，占用的空间是固定的，不会随着事件数量 n 的增加而增加。

本喵的小课堂！

这道题虽然简单，但也能学到不少东西哦！

模拟思想: 很多题目并没有复杂的算法，只需要按照题目的描述，把过程用代码“演”一遍就行。关键在于理清逻辑，不漏掉任何一个细节。
贪心选择: 在每个公交车到来的时刻，我们都只基于当前车站的人数来做判断。这种“只顾眼前”的策略在这里是完全正确的，这就是贪心思想的体现。
仔细读题: 解题的第一步永远是读懂题目！注意到“至少还剩一个空位”和“Monocarp在其他人之后上车”是解题的关键，这直接导出了 seats > current_people 这个核心判断条件。
数据类型选择: 虽然这题 int 也能过，但在比赛中，当数字可能很大时，优先考虑 long long 是一个非常保险的好习惯，可以避免很多不必要的错误，喵！

好啦，这次的题解就到这里啦！希望对你有帮助~ 如果还有不懂的，随时可以再来问本喵哦！加油，你一定可以成为算法大师的！喵~！

J. Waiting for... - 题解 ​

比赛与标签 ​

喵喵，题目在说什么呀？ ​

本喵的思考时间！ ​

代码魔法，变！ ​

效率分析喵~ ​

本喵的小课堂！ ​