[题解]2024CCPC河北省赛-Goose Goose Duck：贪心构造与堆维护的赛时实现拆解-北京尧图网络

1. 从题意到模型Goose Goose Duck 到底在考什么2024 CCPC 河北省赛的 C 题 Goose Goose Duck赛时定位是签到偏中档的构造题。题目大意是有 n 个人编号 1 到 n第 i 个人有一个可加入区间 [l_i, r_i]表示当且仅当当前已经加入游戏的人数落在 [l_i, r_i] 内时这个人才会加入。你要构造一个加入顺序让最终加入的总人数最大。第一次读题容易懵因为「当前人数」是动态变化的而每个人的条件又依赖这个动态值。很多人会下意识想 DP 或者二分图匹配但 n 到 2e5 级别这些方向都会超时。真正要抓的核心是加入过程是一个从 0 开始、每次加 1 的单调递增序列当前人数只会从 0 涨到某个最大值不会回退。这个单调性就是贪心的立足点。把问题抽象一下我们按时间轴枚举「当前人数 k」k 从 0 开始。在人数为 k 的这一刻所有满足 l_i ≤ k ≤ r_i 且还没加入的人都是「当前可加入」的候选。我们要从中挑一个人加入让 k 变成 k1然后继续。目标是让这个过程尽可能长。为什么不能随便挑因为每个人的右端点 r_i 是「deadline」——一旦当前人数超过 r_i这个人就永远没机会了。所以直觉上应该优先把「最快要过期」的人塞进去也就是 r_i 最小的那个。这就是经典的「按 deadline 贪心」和区间调度、任务安排是同一类套路。但这里有个细节候选人是动态出现的。有些人的 l_i 很大当前人数还没到他根本不在候选池里。所以我们需要一个机制随着 k 增大把新满足 l_i ≤ k 的人加进来同时把已经 r_i k 的人踢出去然后从剩下的里挑 r_i 最小的。这个「动态插入取最小删除过期」的组合正是小根堆的拿手好戏。复杂度上每个人最多入堆一次、出堆一次堆操作 O(log n)总复杂度 O(n log n)完全够用。赛时我试过直接暴力每轮扫一遍找最小 rn2e5 时是 O(n²)TLE 得明明白白。所以堆不是炫技是刚需。这一节先把模型立住单调人数轴 deadline 贪心堆维护候选池。后面所有代码和排障都是围绕这三件事展开。你在草稿纸上画一条从 0 到 n 的数轴把每个人的区间画成横条然后想象一条竖线从左往右扫每次挑一条「右端最靠左」的横条——这个画面就是整题的解法。2. 贪心策略的正确性证明与堆维护边界上一节说了「挑 r_i 最小的人」但赛时如果只是凭感觉写很容易在边界上翻车。这一节把正确性和边界讲透你写代码时才知道每一行为什么这么写。先证贪心。假设当前人数为 k候选集合 S { i | l_i ≤ k ≤ r_i, i 未加入 }。设其中 r 最小的人是 x。我们要证明存在一个最优解在 k 这一步选择 x。用交换论证设某个最优解在 k 这一步选了 yy ≠ x之后某一步选了 x如果 x 最终没被选那把这个位置换成 x 只会更优因为 x 的 deadline 更紧。把 y 和 x 的选择顺序交换原来先 y 后 x现在先 x 后 y。交换后x 在 k 时加入满足 l_x ≤ k ≤ r_xy 延后到原来 x 的位置加入此时人数为 k需要验证 l_y ≤ k ≤ r_y。因为 y 原本能在 k 加入所以 l_y ≤ k又因为 k k所以 l_y ≤ k。而 r_y ≥ r_xx 是 r 最小的原来 x 能在 k 加入说明 k ≤ r_x ≤ r_y所以 y 也满足。交换后总人数不变贪心选择不劣。归纳可得贪心最优。证明不复杂但边界才是真正吃分的地方。我踩过的坑主要有三个。第一个坑入堆时机。代码里是while(cnt n v[cnt].l i) pq.push(...)这里 i 是当前人数。注意条件是 i而不是 i。因为 l_i 表示「当有 l_i 人时加入」也就是人数等于 l_i 时这个人就合法了。如果写成 i会漏掉刚好卡在左端点的人。赛时我队友就因为这个 WA 了一发。第二个坑出堆时机。while(pq.size() pq.top().first i) pq.pop();这里是 i因为 r_i 表示「最多到 r_i 人时还能加入」人数等于 r_i 时仍合法超过 r_i即 ≥ r_i 1才失效。所以当当前人数 i r_i 时才弹出。如果写成 i会把刚好卡在右端点的人误删。第三个坑堆的比较器。C 的 priority_queue 默认是大根堆我们要小根堆所以得自定义比较。excerpt 里用的是函数指针bool(*)(pii,pii)配合cmp1写法比较老派。更现代的写法是 lambda 或者重载 operator。但注意如果用 lambdapriority_queue 的模板参数要写decltype(cmp)而且构造函数要传入 cmp容易写错。赛时求稳用函数指针或者直接存负值都行。还有一个隐藏边界当堆为空时直接 break。因为如果当前人数 k 下没有任何候选人说明游戏无法继续后面的人数更大更不可能有人满足l_i 只会更难满足所以直接结束。这个 break 不能省否则会死循环或者越界。把这三个边界记住你的贪心基本就稳了。下一节给完整可复制的代码模板。3. 可复制代码模板与关键样例推演这一节直接上代码。我把 excerpt 里的代码整理成更易读的版本并补上注释和样例推演。你可以直接复制到本地编译。#include bits/stdc.h using namespace std; using ll long long; #define int ll #define endl \n using pii pairint,int; struct node { int l, r, i; }; bool cmp(node a, node b) { if (a.l ! b.l) return a.l b.l; return a.r b.r; } // 小根堆比较器r 小的优先r 相同则编号小的优先 bool cmp1(pii a, pii b) { if (a.first ! b.first) return a.first b.first; return a.second b.second; } void solve() { int n; cin n; vectornode v(n); for (int i 0; i n; i) { cin v[i].l v[i].r; v[i].i i 1; } sort(v.begin(), v.end(), cmp); int cnt 0; priority_queuepii, vectorpii, bool(*)(pii,pii) pq(cmp1); vectorint ans; for (int i 0; i n; i) { // 把左端点当前人数 i 的人加入候选 while (cnt n v[cnt].l i) { pq.push({v[cnt].r, v[cnt].i}); cnt; } // 把右端点当前人数 i 的人踢出 while (pq.size() pq.top().first i) { pq.pop(); } if (pq.empty()) break; ans.push_back(pq.top().second); pq.pop(); } cout ans.size() endl; for (auto x : ans) cout x ; cout endl; } signed main() { ios::sync_with_stdio(0), cin.tie(0); int t 1; while (t--) solve(); return 0; }注意几个点。第一#define int ll是为了防止中间计算溢出虽然本题 n 不大但养成习惯。第二priority_queue的第三个模板参数是函数指针类型bool(*)(pii,pii)构造函数里传入cmp1。如果你用greaterpii会按 first 升序但 second 的次序不确定所以自定义比较器更稳。第三输出格式先输出人数再输出顺序每个编号后跟空格最后换行。赛时如果格式错会 PE虽然现在多数 OJ 对行末空格宽容但养成规范习惯。样例推演。假设 n3区间分别是 [0,1]、[1,2]、[0,2]。排序后按 l 升序人1 [0,1]、人3 [0,2]、人2 [1,2]l 相同按 r 升序。i0把 l≤0 的人入堆人1(r1)、人3(r2) 入堆。堆顶是人1。弹出人1ans[1]。 i1把 l≤1 的人入堆人2(r2) 入堆。堆里有人3(r2)、人2(r2)。堆顶按编号小的优先是人2。弹出人2ans[1,2]。 i2堆里剩人3(r2)。检查 r222 为假保留。弹出人3ans[1,2,3]。最终 3 人全部加入。如果换一个样例n2区间 [0,0]、[0,1]。i0 时两人都入堆堆顶是人1(r0)。弹出人1。i1 时检查堆顶人2(r1)11 为假保留弹出人2。ans[1,2]2 人。如果先选人2i1 时人1 的 r01 被踢只能得 1 人。所以贪心正确。你可以自己造几组小数据手推一遍确认边界。下一节讲怎么验证你的代码。4. 对拍验证与随机数据生成赛时写完代码最怕的是「样例过了但隐藏数据 WA」。构造题尤其如此因为贪心的边界很容易写错。这一节给你一套对拍流程用暴力程序验证贪心程序。暴力思路n 小的时候比如 n ≤ 8直接 DFS 枚举所有加入顺序或者用状压 DP。更简单的是模拟每一步枚举所有当前可加入的人递归尝试取最大值。因为 n 小复杂度可以接受。// brute.cpp暴力搜索最大人数 #include bits/stdc.h using namespace std; int n, ans; vectorint l, r; vectorbool used; void dfs(int cur, int cnt) { ans max(ans, cnt); for (int i 0; i n; i) { if (!used[i] l[i] cur cur r[i]) { used[i] true; dfs(cur 1, cnt 1); used[i] false; } } } int main() { cin n; l.resize(n); r.resize(n); used.assign(n, false); for (int i 0; i n; i) cin l[i] r[i]; ans 0; dfs(0, 0); cout ans endl; return 0; }然后写一个随机数据生成器// gen.cpp #include bits/stdc.h using namespace std; int main() { srand(time(0)); int n rand() % 8 1; cout n endl; for (int i 0; i n; i) { int a rand() % (n 1); int b rand() % (n 1); if (a b) swap(a, b); cout a b endl; } return 0; }对拍脚本Windows 下用 batLinux 下用 sh#!/bin/bash for i in $(seq 1 1000); do ./gen in.txt ./brute in.txt out1.txt ./greedy in.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo Difference found at test $i cat in.txt break fi done echo Done注意暴力程序输出的是最大人数贪心程序输出的是人数顺序。对拍时只比较第一行的人数即可或者把贪心的第一行单独提取。我一般让贪心程序也输出人数然后 diff 第一行。跑个几百组如果全部一致基本可以放心。如果发现不一致把出错的输入保存下来手推一遍通常就是前面说的三个边界之一。我实测下来最容易错的是出堆条件写成 i导致卡右端点的人被误删人数偏少。对拍不仅能验证正确性还能帮你理解贪心的适用边界。比如当区间出现 l_i r_i 的非法输入时你的程序会怎么处理题目保证合法但你可以故意造这种数据看看会不会崩。这种「破坏性测试」能让你对代码的鲁棒性更有信心。5. 常见报错与排障从 WA 到 AC 的排查清单这一节把赛时可能遇到的报错和排查路径列清楚。构造题的报错往往不是编译错误而是逻辑错误所以排查要靠对拍和手推。报错一WA on test 2人数偏少。最常见的原因是出堆条件写错。如果你写成while (pq.size() pq.top().first i) pq.pop();那么当 r_i i 时这个人会被误删。正确写法是 i。检查你的代码把改成。报错二WA人数偏多或顺序非法。可能是入堆条件写错。如果你写成v[cnt].l i会漏掉 l_i i 的人导致候选池偏小人数偏少如果你写成v[cnt].l i 1会提前把还没到左端点的人入堆导致选了不合法的人顺序非法。正确写法是v[cnt].l i。报错三RE运行时错误。常见于堆为空时没有 break继续访问pq.top()。检查你的代码在if (pq.empty()) break;之前不要调用pq.top()。另外如果 n0循环不会执行输出 0 和空行一般没问题。报错四TLE。如果你没用堆而是每轮扫一遍数组找最小 r复杂度 O(n²)n2e5 时必超时。检查你是否用了priority_queue。另外ios::sync_with_stdio(0), cin.tie(0);要加上否则读入慢也可能 TLE。报错五PE格式错误。输出顺序时最后一个编号后面有没有空格多数 OJ 宽容但有些严格。建议统一写成for (auto x : ans) cout x ; cout endl;行末多一个空格通常没事。如果 PE检查是不是少了换行或者多了空行。报错六编译错误。如果你用 lambda 作为 priority_queue 的比较器模板参数要写decltype(cmp)而且构造函数要传cmp。例如auto cmp [](pii a, pii b) { return a.first b.first; }; priority_queuepii, vectorpii, decltype(cmp) pq(cmp);注意decltype(cmp)不带引用且pq(cmp)要传实例。如果写成priority_queuepii, vectorpii, decltype(cmp) pq;会编译错误因为 lambda 没有默认构造函数。赛时求稳用函数指针或仿函数。报错七逻辑正确但对拍不过。检查你的暴力程序是否正确。暴力程序如果也写错对拍就没意义。建议先用题目样例验证暴力程序再用暴力验证贪心。排查顺序建议先看样例再看边界手推再对拍最后看复杂度。大部分 WA 都能在前两步解决。如果实在找不到把代码打印出来逐行对照本文的边界说明通常能发现和的混淆。6. 同类构造题的复用思路与练习建议Goose Goose Duck 这类题核心套路是「单调轴 deadline 贪心堆维护」。这个套路在 CCPC 和 ICPC 里反复出现只是换了个皮。比如「任务安排」类题每个任务有开始时间和截止时间问最多能完成多少任务或者「会议室安排」每个会议有开始和结束时间问最多能安排多少场。解法几乎一模一样按开始时间排序枚举当前时间把开始的会议入堆把结束的踢出选结束最早的。区别在于Goose Goose Duck 的「当前时间」就是「已加入人数」是离散的整数而且每个人的「开始时间」l_i 和「截止时间」r_i 都依赖这个人数。这种「依赖当前状态」的设定让题目多了一层构造的味道但贪心本质没变。如果你想练同类题建议按这个顺序先做经典的「区间调度最大不相交区间」再做「带 deadline 的任务安排」最后做本题。每道题都手推一遍贪心正确性再用对拍验证。练多了你会发现看到「最多能选多少个」「有截止时间」「动态候选」条件反射就是堆贪心。另外构造题的输出往往不唯一OJ 通常用 special judge 检查。所以你的顺序只要合法且人数最大即可不必和标准答案一样。赛时如果卡在输出格式先确认人数对不对人数对了再调顺序。最后给一个实用技巧写贪心题时先在草稿纸上画数轴和区间把贪心策略用一句话写下来再写代码。代码写完先跑样例再手推边界再对拍。这三步做完基本不会翻车。Goose Goose Duck 作为签到题赛时应该控制在 20 分钟内 AC如果你花了更久多半是边界没想清楚。把本文的边界清单背下来下次遇到同类题直接套。如果你想把这类题练得更熟可以到 TaoToken 的模型对话里让模型帮你生成几组随机数据或者用 Coding Plan 把对拍脚本自动化。接入方式很简单在 API Keys 页面拿到 KeyBase URL 填https://taotoken.net/api模型选一个擅长的就能把生成器和暴力程序串起来跑。具体配置参考接入文档这里不展开。重点是贪心堆的模板要练到肌肉记忆赛时才能稳。

[题解]2024CCPC河北省赛-Goose Goose Duck：贪心构造与堆维护的赛时实现拆解

相关推荐

浙江EAC认证代办怎么选？这份避坑指南请收好

128路矩阵开关：把测试系统的物理接线变成软件路由

Java类加载机制详解：双亲委派、类初始化与异常排查

更多资讯

基于Falsk+ResNet34+Kimi宠物皮肤病智能诊断系统

【芳心科技】F. 雷达波扫描非接触式睡眠监控系统设计与实现

DRSformer·论文蒸馏笔记：可学习 Top-k 稀疏注意力去雨网络

08.【网络】Linux进程组、会话、作业控制与守护进程核心知识点 - 进程在终端中到底是怎样组织的

GD32C231+CS43198音频项目踩坑全记录：I2C从机SCL卡死、音量逻辑混淆、HID指令适配全套解决方案

精灵永恒正版官方客户端下载指引，忆往游戏正规安全渠道指南

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？