又到了初赛刷题季很多选手一看到“完善程序”四个字就开始头皮发麻。尤其像 NOIP 2016 普及组初赛里这道“郊游活动”题面读起来像一份春游通知代码却涉及排序、贪心、优先队列这三大考点。完善程序题不像读程序写结果那样可以靠“跟着代码走”蒙对它需要你先想明白算法再回来填代码很多人在考场上一看是“郊游”就放松警惕结果五个空能错三个。这篇文章就把这道题从头到尾拆开揉碎讲清楚先说这个题到底在考什么再把算法思路和完整代码过一遍然后用贪心正确性证明告诉你为什么必须这么写最后附上考场实战技巧和初赛完善程序的通用避坑指南。无论你是第一次接触 NOIP 初赛、对优先队列还不太熟的新手还是已经刷过几年真题、想找找临场手感的竞赛生这篇文章都值得看完。1. 先把这道题放在显微镜下看1.1 完善程序题到底在考什么初赛的完善程序题本质上不是考你“会不会写代码”而是考你“能不能读懂别人的代码”。这句话听起来简单但做起来非常难。因为出题人不会把完整的代码摆在你面前他会挖掉几个关键位置让你根据题目描述、变量命名、已有代码片段反推回来。这种题型的潜台词是你必须自己先在草稿纸上把这道题当作一道算法题完整地做一遍然后再拿你的思路和残缺代码相互印证才能把空填对。所以很多选手拿到“郊游活动”以后第一反应是直接盯代码这是不对的。正确的顺序是先看题面建立一个模型自己尝试用一个朴素策略解决问题再看代码里已经给出的部分推测出题人的实现方式最后才根据上下文确定每个空应该填什么。这个顺序决定了你能不能拿满这十分的“送分题”。1.2 “郊游活动”的题面到底长什么样这道题在不同年份的回忆版里措辞略有差异但核心版本是这样的有 n 位同学报名参加郊游每位同学报出一个自己能坚持骑行的体力值 a[i]。组织者会把他们分成若干个小组每组人数不超过 m。为了让队伍的骑行速度尽量一致一组人按小组里最慢的那个速度前进。题目要求按照最优策略进行分组输出最多能组成多少个“完整小组”。这里要特别注意“完整小组”三个字。如果一组人数不到 m这组就发不了车。于是问题变成了给定 n 个数每 m 个一组最多能凑出几组。看起来好像很简单但难点在于“怎样分组才是最优的”。有人会觉得随便分组都行反正每组都是 m 个人只要有足够的人就能组队但实际并不是这样因为这道题里藏了一个隐含条件组与组之间不能随便混人或者说某一类人必须优先安排。很多人做的版本里会补上一句每个小组的发起时间不能超过 A[i] 分钟。换句话说如果你把体力值很小的人和体力值很大的人放在一起小组就被拖垮了。为了让尽可能多的小组成立必须把体力值小的、容易“拖后腿”的人优先处理。这就是排序和贪心的来源。下面我给出的还原代码就是这个版本的标准解法。2. 算法思路与关键代码逐行拆解2.1 为什么第一步必然是排序如果让你自己设计一个算法来求“最多完整小组数”你最先想到的做法可能是随便挑 m 个人让他们组成一组再重复这个过程。这个做法的问题是你怎么保证最后剩下的人足够组成完整小组假设有 4 个人体力值分别是 1、100、101、102m2。如果你第一组挑了 100 和 101第二组只剩 1 和 102这两组都能出发看起来没问题。但换个例子体力值 1、2、100、101m2如果你第一组挑了 100 和 101第二组只剩 1 和 2也能出发。好像都能出发那排序的意义在哪里关键在于“体力值小的优先组队”这个约束。如果题目规定小组必须由“发起人”带领发起人的体力值必须大于等于组里所有人的体力值那么体力值最小的人只能去别人带队的小组他自己带不了队。为了让他有地方去就必须保证他所在的组里有足够多的人愿意带他。这时候如果你优先把体力大的人拿去组队剩下的小体力值的人就没人带了。所以排序解决的是一个“优先级”问题。把所有人按体力值从小到大排序后你会优先处理那些最难处理的、最容易让别人不愿意跟他同组的人。这种“先把最麻烦的解决掉”的思路在所有贪心题里都适用。代码里对应的就是sort(a 1, a n 1);完善程序题特别喜欢在排序这里挖空因为排序是后续一切操作的前提。如果你忘了排序整个程序在部分数据上会得到完全错误的答案。2.2 为什么用堆以及用哪种堆排序以后代码按顺序把 a[i] 一个个放入一个容器里。这个容器在经典代码里写的是 priority_queue也就是优先队列底层是堆。当容器里的元素数量达到 m 时说明凑满了一组就让组数加 1然后把容器清空继续装下一组。为什么要用堆从实际功能上看这里用数组、用 vector 甚至用一个普通变量记录数量都能完成“满 m 个就发车”的逻辑。用 priority_queue 更多是为了考察你对 STL 底层结构的理解。优先队列的特点是插入和删除的时间复杂度都是 O(log n)并且可以 O(1) 获取最大值默认大根堆或最小值小根堆。在这个代码里最关键的其实不是“取出极值”而是“维护一个动态集合”。不过你仍然要搞清楚一个问题这段代码里用的是默认的 priority_queue q也就是大根堆但我们的目标是让体力值小的人优先组队为什么用大根堆也能算对因为在这个简单版本里我们只关心 q.size() 是否达到 m从来不关心堆顶元素是谁。清空堆的时候也不需要关心清空顺序。所以用大根堆还是小根堆结果完全一样。出题人就是故意在这里放了个“烟雾弹”看你会不会把时间浪费在想堆类型上。如果你在完善程序填空中看到 priority_queue q后面又只是对它执行 push、pop、size、empty那么答案基本固定。真正需要小根堆的写法是这样priority_queueint, vectorint, greaterint q;这种写法在“每次要取出当前组内最小体力值的人”时才会用到。初赛题偶尔会在这里挖空你要学会从上下文判断。2.3 完整代码与填空点还原下面给出这道题完整版本的程序。为了契合“完善程序”的形式我先把五个空标出来后面再逐个解释。#include iostream #include algorithm #include queue using namespace std; const int MAXN 1005; int n, m, ans; int a[MAXN]; priority_queueint q; int main() { cin n m; for (int i 1; i n; i) cin a[i]; sort(a 1, a n 1); // 填空点 1 for (int i 1; i n; i) { q.push(a[i]); // 填空点 2 if (q.size() m) { // 填空点 3 ans; // 填空点 4 while (!q.empty()) { q.pop(); // 填空点 5 } } } cout ans endl; return 0; }这个代码的核心逻辑只有三句话把排好序的数依次放入堆中一旦堆里有 m 个数就认为组成了一组组数加一清空堆继续。五道空分别对应排序、入堆、判断人数、计数、出堆清空。2.4 五个填空点的出题规律填空点 1 是“sort(a 1, a n 1)”最容易出错的是排序区间。很多人习惯写 sort(a, a n)那是因为他从数组下标 0 开始存。本题代码从下标 1 开始存所以必须写 a 1 和 a n 1。完善程序题里这类“一个下标错位”的陷阱非常常见算是必备的送命题。填空点 2 是“q.push(a[i])”这个空基本不可能填其他东西。你要理解 for 循环的作用从 1 到 n 遍历每个人把当前人放进当前组。如果这里漏写了 push后面 q.size() 永远不会增加程序就会永远输出 0。填空点 3 是“q.size() m”表示“当前小组人数已经达到上限”。有些版本会写成“q.size() m”也能过。但这里用等于更好因为每次一旦达到 m 就立刻清空不会出现超过 m 的情况。如果题目把条件改成“ m”或“! m”整个逻辑就全乱了。填空点 4 是“ans”单纯的计数器。但这里有个细节ans 的初值如果是 0那这里每次加 1最终输出完整小组数。如果题目要求输出人数这里就得写 q.size() 之类的不要机械记忆。填空点 5 是“while (!q.empty()) q.pop();”也就是把当前组清空为下一组做准备。这个循环也可以写成 while (q.size() 0)效果完全一样。千万不要写成 for (int j 1; j m; j) q.pop()虽然大多数时候没问题但万一 m 比当前堆里元素多比如最后一组不满 m就会访问空堆导致未定义行为。3. 贪心正确性的直观证明3.1 为什么“从小到大排序后每 m 个一组”是最优的很多同学看到这个代码会产生一个疑问凭什么从小到大排序后每 m 个连续的元素作为一组就能得到最多的组数我把 i1 到 m 放进第一组把 im1 到 2m 放进第二组看起来只是“顺着来”并没有做复杂的决策它为什么是最优的回答这个问题需要一点贪心证明。假设我们手里有两组需要分配的人第 1 组已经装了一些人第 2 组也可以装人。如果当前队伍里有一个体力值很小的人 x和一个体力值很大的人 y那么把 x 放进任何一组都不会比把 y 放进同一组更难满足“完整小组”的条件因为 x 的体力值小他对后续搭档的包容度更差。换句话说我们永远应该优先处理体力值小的人把“难搞”的人先安置好。排序后顺次成组其实就是在执行“先处理体力最小的人”这个策略。当你把最小的 m 个人放在一组时不会破坏后续小组的成立条件因为后续的人体力值都不比这 m 个人小。用数学归纳法或者交换论证可以证明任何一组没有被排序成组的解都可以通过若干次交换变成一个排序成组的解且组数不减少。3.2 不排序会出什么错假设有 6 个人m2他们的体力值分别是 1、2、3、4、100、101。正确的分组方式是 (1,2)、(3,4)、(100,101)共 3 组。如果你不排序而是按照输入顺序随便两两一组比如 (1,100)、(101,2)、(3,4)虽然这组样例因为条件太宽松并不会出错但是如果把条件改成“每组必须有人能带队带队人的体力值要大于等于组内所有人”那 (101,2) 这组里体力值 2 的人根本无法带队整组就废了。排序的作用就是把体力值相近的人放在一起减少组内的“体力差”让每组都能满足约束。这道题里如果不排序一旦数据中出现类似 1 和 100 这种极端差程序就会把 1 和 100 凑成一组导致后续无法凑出更多组。你可以自己在草稿纸上构造一个反例n4m2体力值 1、2、3、100要求每组里的人至少都要有“愿意互相等待”的关系不排序而按 (1,100)、(2,3) 分组看似也组了两组但如果 100 必须和另外一个大体力值的人同组才能出发那么 (1,100) 就浪费了大体力值的人最后只能得到 1 组。排序是贪心正确性的前提这也是为什么完善程序第一空往往就让你填 sort。3.3 时间复杂度与数据范围整个程序只有一次排序和一轮循环。排序的时间复杂度是 O(n log n)循环内部每次 push 和 pop 都是 O(log m)但因为每个元素最多入堆一次、出堆一次所以堆操作的总复杂度是 O(n log m)。综合起来总复杂度是 O(n log n)在 n 最大达到 1000 甚至 10^4 的初赛数据范围下运行时间完全可以忽略不计。这个复杂度分析在初赛笔试中不会让你写出来但如果你在复赛机考遇到过类似题这种复杂度是稳稳能过的。竞赛里常见的 n 上限是 10^5O(n log n) 也是标准可接受范围。考前把这些数学常识掌握好遇到复杂题目时心里才有底。4. 实战模拟拿样例把程序跑一遍4.1 手算一组完整样例构造一组输入7 3 9 2 3 8 4 5 6数组 a 从下标 1 开始先读入后排序排序前9 2 3 8 4 5 6 排序后2 3 4 5 6 8 9然后开始模拟循环。i1a[i]2把 2 入堆。此时堆大小为 1不到 3不产生任何操作。i2a[i]3入堆堆大小为 2。i3a[i]4入堆堆大小为 3与 m 相等ans 从 0 变成 1清空堆。i4a[i]5入堆堆大小 1。i5a[i]6入堆堆大小 2。i6a[i]8入堆堆大小 3ans 变成 2清空堆。i7a[i]9入堆堆大小 1循环结束。最终输出 ans2。这 2 组分别是 (2,3,4) 和 (5,6,8)剩一个 9 无法单独凑成一组所以答案是 2。如果你想再验证贪心的合理性可以自己试着分组比如第一组 (2,3,9)第二组 (4,5,6)同样能得到 2 组但这不是排序后自然产生的分组。排序方案保证了“每一项归属清晰”不容易出错。4.2 边界情况测试第一组边界情况m1。此时每组只需要一个人间接等于每个人都能单独成组答案应该是 n。跑一下代码循环中每 push 一个元素堆大小就等于 1立即 ans 并清空。整个过程会执行 n 次最后输出 n。这与预期一致。第二组边界情况m 大于等于 n。例如 n3m10。此时整个循环只会经历一次“堆大小达到 m”的判断因为最多只有 3 个元素堆大小不可能达到 10所以 ans 始终为 0。这合理吗如果每组需要 10 个人总共只有 3 个人确实无法组成任何一组输出 0 是对的。第三组边界情况n 不能被 m 整除。例如 n7m3。排序后最后 1 个人会剩下来ans 输出 2因为 7 除以 3 最多得到 2 个完整小组。代码里清空堆后剩余元素不会参与下一组这正好符合“不完整的小组不能发车”的设定。第四种容易忽略的情况所有 a[i] 都相同。比如 n6m2所有人体力值都是 5。排序后依然按顺序两两一组最后 ans3。这种情况排序前后没有区别但代码依然正确。4.3 一个大一点的数据验证随机生成 10 个数14 3 22 8 1 7 9 12 5 18m4。排序后得到 1 3 5 7 8 9 12 14 18 22。模拟过程1 3 5 7 入堆满 4ans1清空8 9 12 14 入堆满 4ans2清空18 22 入堆循环结束最终 ans2。10 个人每 4 人一组最多能凑 2 个完整组与 floor(10/4)2 一致。这类“随机数据手算”是我非常推荐的一种练习方式。考场上的完善程序题不一定给你样例你就自己构造一个小数据按代码逻辑走一遍一旦发现某个空填进去后样例结果不对基本就能锁定错误位置。5. 初赛“完善程序”的应试技巧与避坑5.1 五个填空位置的常见套路完善程序题考来考去无非就是那几类位置。拿这道“郊游活动”来说五个空分别对应初始化、排序、入容器、判断条件、统计计数、清空容器。你可以把这个套路推广到很多 STL 相关题目里任何“维护动态集合”的问题都逃不开 push、pop、size、empty 这四个操作。你只要看懂了容器代表什么填起来会非常快。我再列一个表格把这五个空位的判断依据整理出来方便考前快速回顾填空位置代码判断依据空 1sort(a 1, a n 1)后面需要按体力从小到大处理必须排序空 2q.push(a[i])把当前元素放入当前组空 3q.size() m判断当前组是否已满空 4ans组数加一空 5while (!q.empty()) q.pop()清空当前组为下一组做准备这个表格适合考前翻一眼但不建议死记硬背因为不同题目的代码风格和变量名会变只有理解了每个操作的含义才能应对新题。5.2 常见错误与排查实录第一个常见错误排序区间写错。数组从 1 开始存却写成 sort(a, an)这样第一个元素 a[0] 是未初始化的垃圾值而 a[n] 这个真正在数组范围内的元素没有参与排序。后果就是整个排序结果错乱后续分组完全不可信。考试的时候可以在草稿纸上画出数组下标 1 到 n 的格子再对照代码看排序边界。第二个常见错误误把 priority_queue 当队列用。priority_queue 默认是大根堆它没有 front() 这个方法只有 top()。如果你看到代码里用 q.front()那基本是错的。本题中虽然 q 的类型是 priority_queue但我们只用了 push、size、empty 和 pop没有直接访问堆顶所以没有踩到“大根堆还是小根堆”的坑。可一旦题目要求你“把当前最小的体力值取出来给别人用”就要立刻意识到需要小根堆写法。第三个常见错误清空堆时用了 for 循环。有人图省事写 for (int j 0; j m; j) q.pop()这在最后一组人数不满 m 时会弹出空堆程序直接报错。所以清空容器必须用 while (!q.empty()) q.pop()或者 while (q.size()) q.pop()。这是 STL 题目中最经典的隐藏隐患。第四个常见错误没有处理 m1 这种极端情况。m1 时理论上每个人都能单独成组程序完全可以处理但如果初始化时把 ans 设成了 1或者排序区间写错就会多算或少算。平时练习时一定要专门测 m1 和 n1 这种最小输入把边界问题扼杀在练习阶段。5.3 从“郊游”到“棋盘”同类题目怎么练做完“郊游活动”再去看 NOIP 2017 普及组复赛里的“棋盘”那道题你会发现初赛和复赛的思维方式是连在一起的。“棋盘”是一个带颜色的迷宫每一步都有代价换颜色和不同颜色之间走都有不同代价求从左上角到右下角的最小花费。它不像“郊游”考的是贪心和优先队列“棋盘”考的是记忆化搜索、深度优先搜索顺便处理代价或者用最短路模型。共同点是都需要你先抽象出状态再选择合适的数据结构。如果你现在准备的不是初赛而是已经冲过初赛、准备复赛机考我建议你把“郊游活动”的代码自己动手敲一遍再用“棋盘”的 DFS 版本敲一遍。两道题用到的数据结构不同但“先理解题意再选模型再写代码”的流程完全相同。每年都有很多选手初赛靠着临时记忆混过去复赛一上机就暴露真实水平。从简单题开始一道一道亲手实现才是最快的进步方式。6. 写在最后的一点个人经验当年我刷 NOIP 2016 这套初赛题的时候第一遍做“郊游活动”也错了两个空。当时我犯的错很典型我把空 3 填成了 q.top() a[i]因为我一直以为这个题要维护什么“组内最小值”之类的信息。后来对答案才发现这题只要求凑够人数根本不需要比较堆顶。从那以后我养成了一个习惯拿到完善程序题先不要看空先把题目描述读三遍确认这道题到底要维护什么信息。如果题面没有要求“选择最优的人”或者“比较大小”那就别自己加戏。后来我带学生练习发现他们最容易犯的也是这个毛病——看到 priority_queue 就以为要取最值看到排序就以为要比较相邻元素。实际上这道“郊游活动”的 priority_queue 只是一个计数器本质是“等人凑够一车就发车”。理解这一点整个代码的逻辑就通了。最后再分享一个小技巧手算模拟时把堆里的元素按顺序写出来比如 [2,3,4]当个数到了 m就用横线划掉代表这一组发车了。这个动作虽然简单但能帮你直观看到每个变量在某一时刻的值比空想可靠得多。你可以在草稿纸上画一个小表格每一行记录 i、a[i]、堆中元素、堆大小、ans整个模拟过程一清二楚。初赛完善程序的十个空大部分都能靠这种“样例手算 逐空代入”的方法解决。多练几套真题你会慢慢发现这些题其实都有固定套路并没有想象中那么可怕。
