20260328：AtCoder Beginner Contest 451

百会（bestWit）| 百炼成钢，融会贯通，助力GESP备考

哈喽，备战GESP的同学们～ 百会（bestwit）AtCoder题解来啦！每周1次更新，聚焦竞赛高频题型，贴合GESP入门难度，帮大家拆解解题思路、掌握解题技巧，夯实编程基础，为GESP考试做好准备。

题目

题目编号：C - Understory  题目难度：★★★☆☆（贴合GESP 4-5级难度） 题目链接：C - Understory

题目大意

高桥君正在管理院子里的树木数量。初始时院子里没有树。
接下来会按顺序给出 QQ 个操作，每个操作是以下两种类型之一：

1. 1 h：在院子里种一棵高度为 hh 的树。
2. 2 h：砍掉院子里所有高度小于等于 hh 的树。

对于每个操作，请在处理完该操作后，立即输出院子里剩余的树的总数量。

解题思路

我们需要维护一个数据结构来存储当前院子里所有树的高度，并且需要支持两种操作：

1. 添加元素：将一个新的数值（树的高度）加入集合。
2. 阈值删除：删除集合中所有小于等于某个特定值 hh 的元素。
3. 查询大小：获取当前集合中元素的数量。

数据结构选择：
由于操作 2 需要删除所有“高度 ≤h≤h ”的树，如果我们能快速访问当前最小的高度，就能高效地判断是否需要删除。

• 如果使用最小堆（优先队列），堆顶元素永远是当前树中最矮的。
• 当执行操作 2 时，我们只需要不断检查堆顶元素：
  • 如果堆顶元素 ≤h≤h ，说明这棵树需要被砍掉，将其弹出堆。
  • 重复此过程，直到堆为空，或者堆顶元素 >h>h （说明剩下的树都比 hh 高，不需要删除）。

因此，使用 C++ 的 priority_queue 并将其配置为最小堆是解决此问题的最佳方案。

代码

#include <bits/stdc++.h>

using namespace std;

// t: 操作次数 Q
// x: 操作类型 (1 或 2)
// h: 树的高度
long long t, x, h;

// 定义一个小顶堆（最小优先队列）
// 默认是大顶堆，使用 greater<long long> 可以将其变为小顶堆
// 这样 q.top() 始终是当前院子里高度最小的树
priority_queue <long long, vector<long long>, greater<long long>> q;

int main() {
    // 读取操作总数
    cin >> t;
    
    // 循环处理每一个操作
    while (t--) {
        // 读取操作类型 x 和高度参数 h
        cin >> x >> h;
        
        if (x == 1) {
            // 操作类型 1: 种树
            // 将高度为 h 的树加入优先队列
            q.push(h);
        } else if (x == 2) {
            // 操作类型 2: 砍树
            // 当队列不为空 且 当前最矮的树高度 <= h 时，执行删除
            while (!q.empty() and q.top() <= h) {
                q.pop(); // 弹出堆顶元素（砍掉这棵树）
            }
        }
        
        // 输出当前院子里树的数量（即优先队列的大小）
        cout << q.size() << "\n";
    }
    return 0;
}

关键点总结

• 小顶堆的使用：利用 priority_queue<Type, Container, Greater> 语法创建小顶堆，使得我们可以总是优先处理（删除）高度最小的树。
• 贪心策略：在删除操作中，因为要删除所有 ≤h≤h 的树，而堆顶是最小的。如果堆顶都大于 hh ，那么堆里剩下的所有树肯定都大于 hh ，可以直接停止删除。
• 变量类型：虽然题目中 hh 的范围在 int 内，但代码中使用了 long long，这是一种安全的编程习惯，防止潜在的溢出问题（尽管在此题中 int 也足够）。

最后，祝大家在后续的AtCoder比赛中，顺利AC每一道C题，稳步提升！后续我们会逐步更新难度更高的题解，贴合GESP进阶考点，陪大家一起“百炼成钢”。

下期预告：AtCoder Beginner Contest 452，经典的 300 点模拟类题目，记得关注公众号，第一时间获取更新通知～