P4447 [AHOI2018初中组] 分组是洛谷题库里一道很经典的中等偏易的贪心题。我第一次在题目列表里看到它时以为只是“把大小接近的数放一起”结果按这个思路写完直接WA。后来把题意逐句拆开又把几个样例手动跑了三轮才真正理解它考核的并不是排序而是如何动态维护一组“已经开好但还没结束”的序列让它们尽量均衡地生长。这篇文章面向刚开始刷贪心的同学也适合那些和我一样一上来就被“最少组的最大人数”绕晕的人我会把思路、代码和调试过程完整写出来希望能帮你少走一点弯路。1. 题目拆解到底在求什么1.1 题面还原题目大意是这样的给定 n 个整数a[i] 表示每个人的能力值。要把 n 个人分成若干组每一组必须满足一个硬性条件组内所有人的能力值互不相同并且从小到大排好后正好是连续的一段比如 {1, 2, 3} 合法{1, 3} 不合法{2, 2} 更不合法。每个人只能属于一个组每个数用到一次就不能再用。在此基础上题目要求两个层次的最优目标第一分组数尽量少第二在分组数已经最少的前提下人数最少的那个组人数要尽量多。最后输出这个“最短组的人数”。这个二级目标非常关键很多人一上来只看后面的“最短组最大”忽略了“组数最少”导致思路完全跑偏。1.2 用一句话概括核心矛盾假设没有任何限制我们可以把每个人单独分成一组那最短组人数永远是 1但这显然不是我们想要的。所以“组数尽量少”其实是在逼着我们把能合并的数尽量往一个组里塞而“最短组最大”则是在提醒我们合并的时候不能只顾着减少组数还要照顾那些“发育不良”的小组。举个例子如果有六个数字 1、1、2、2、3、3你可以把它们分成两组{1, 2, 3} 和 {1, 2, 3}。这样组数是最少的 2 组最短组的人数是 3答案就是 3。但如果你贪心地把第一个 1、第一个 2、第一个 3 组成一组剩下的 1、2、3 依然能组成一组结果同样是最短组 3。这里数字少看不出特别大的差别但一旦数字多起来分配方式不同最短组长度会差很多。1.3 哪些常见思路会翻车我第一次做这道题时第一反应是排序然后从左往右扫描碰到不连续的就断开开新组。这个思路在数字全部不重复的情况下是对的但一旦出现重复数字比如两个 1、两个 2扫描时看到第二个 1 就必须断开可接下来第二个 2 到底该接在哪个组后面扫描法根本没法维护“多个候选组”的信息。还有人会往 DP 方向想用 dp 值表示前 i 个数分完后的最短组长度。但仔细一想分组方式是不确定的值域也可能很大DP 状态里面要记录的东西太多了根本不现实。其实这道题的正确姿势是贪心而且需要用一个数据结构来动态维护所有“还没封口”的组。2. 贪心策略的推导为什么是“末尾值 人数”这个组合2.1 从“当前这个数能做什么”入手我们把所有数字从小到大排序后从左到右逐个处理思考此时遇到一个数字 x它有哪些去处第一种x 可以接在某个组的末尾但前提是这个组当前的末尾值必须是 x - 1。比如 x 是 3那只能接在末尾为 2 的组后面变成末尾为 3 的组接在末尾为 1 的组后面中间缺了 2组就变得不合法了。第二种x 找不到任何一个末尾为 x - 1 的组那么它只能自己开一个新组暂时作为这个组的开头。这也很好理解既然没有组能接住我我只能自己去当“第一个吃螃蟹的人”。这里有一个非常容易被忽略的点如果一个组的末尾值已经小于 x - 1那么这个组就永远“封口”了。因为后面的数字一定大于等于 x不可能凭空给它补上 x - 1 和 x 之间的空隙所以这个组已经不可能再变长。处理当前数字时必须先把这些失效的组从候选池里扔掉不然会干扰后续判断。2.2 当有多个组都能接住 x 时选哪个假设现在有三个组末尾都是 2人数分别是 1 人、4 人、6 人而当前 x 是 3。这三个组都能接住 3我们应该接谁如果接在 1 人的组上这个组变成 2 人不再是全场最短如果接在 6 人的组上6 人组变成 7 人那个 1 人组还是孤零零的最后答案里最短组很可能就是 1。很明显为了保证最终“最短组尽量长”我们应该优先把 x 送到人数最少的那个组手里让它尽快摆脱“垫底”的命运。这就是这道题贪心策略的核心能接就接接的时候优先接最短的。2.3 用优先队列维护候选组既然需要在多个候选组里快速找到“末尾为 x - 1 且人数最少”的组自然就想到堆。我们可以把每个组表示成一个二元组 (last, cnt)last 表示这个组当前的末尾值cnt 表示这个组当前的人数。堆的排序规则必须想清楚第一关键字是 last越小越靠前在 last 相同的情况下第二关键字是 cnt越小越靠前。为什么要把 last 放在第一位因为“能不能接”是硬约束last 不同就不能接只有当 last 相同时才去比较人数来选最优。这个顺序一旦写反比如先按 cnt 排序堆顶可能是一个 last 不满足条件的短组贪心就直接失效了。每次拿到 x 时我们先把堆顶所有 last x - 1 的组全部弹出因为你已经处理不到它们了。然后再看当前堆顶如果堆顶的 last 恰好等于 x - 1说明它就是所有可接组里人数最少的那一个弹出它把它的 cnt 加 1再把 (x, cnt 1) 重新压回堆里如果堆顶的 last 不等于 x - 1也就是说没有可接的组就压入 (x, 1) 开新组。3. 核心实现C 代码逐行解读3.1 完整代码#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; for (int x : a) { // 先把所有已经无法接续的组扔掉 while (!pq.empty() pq.top().first x - 1) { pq.pop(); } if (!pq.empty() pq.top().first x - 1) { auto cur pq.top(); pq.pop(); pq.push({x, cur.second 1}); } else { pq.push({x, 1}); } } int ans n; while (!pq.empty()) { ans min(ans, pq.top().second); pq.pop(); } cout ans endl; return 0; }3.2 为什么用 pairint,int 加 greater 就行C 的优先队列默认是大根堆也就是队列顶部是最大值。要变成小根堆第三个模板参数传 greater。而对 pairint,int 来说greater 会让它先比较 firstfirst 相同再比较 second这正好满足我们“末尾值优先、人数次之”的需求。如果你觉得这样写有点隐晦也可以自己定义一个结构体重载 operator()逻辑更清楚struct cmp { bool operator()(const pairint,int a, const pairint,int b) const { if (a.first ! b.first) return a.first b.first; return a.second b.second; } }; priority_queuepairint,int, vectorpairint,int, cmp pq;这个 cmp 的返回值表示“a 应该排在 b 后面”所以 a.first b.first 表示 first 大的往后排实现的就是小顶堆。两种写法效果一样但从代码可读性来说自定义 cmp 更推荐给初学者。3.3 两个关键分支接续和开新组先看 while 循环。这里很多人会写成while (!pq.empty() pq.top().first x)这是一个经典大坑。假设当前 x 是 3如果堆顶 last 是 2按 x的条件判断2 3 成立就会把 last 为 2 的组弹出去结果 x 3 本来可以接在末尾为 2 的组后面却没得接了只能开新组答案直接错乱。正确的弹出条件应该是 x - 1只有 last 小于 x - 1 才说明这个组彻底接不上而 last x - 1 正是我们可以接续的对象。再来看 if 分支。堆顶 last 等于 x - 1 时我们弹出它然后 push 一个新的二元组 (x, cnt 1)。这里必须弹出再 push不能直接修改堆顶的值因为堆结构不允许随意更改元素。有些新手第一次写会想着pq.top().second这在优先队列里是完全非法的因为 top() 返回的是 const 引用。如果堆顶 last 不等于 x - 1那就说明当前堆里没有任何一个组能接住 x之前小于 x - 1 的全被弹走了现在堆顶要么大于 x - 1要么堆为空此时必须开新组 (x, 1)。3.4 最后统计答案处理完所有数字后优先队列里的每个元素都代表一个最终组。此时直接遍历堆把所有 cnt 取最小值即可。为什么这里不会再有“失效组”干扰因为在处理后续更大数字时那些失效组已经被 while 循环弹掉了还留在堆里的都是正常结束的组。答案初始值我习惯设为 n因为任何组人数都不可能超过总人数 n这样取 min 一定安全。也可以初始化成 INT_MAX本质没有区别。如果你的题目输入可能 n 0那要单独特判但一般竞赛题不会出现空输入。4. 样例手推与复杂度分析4.1 冒烟测试样例1 1 2 2 3 3我用这组数据做了很多次验证因为它能很好地体现“多个组竞争同一个 x”的场景。排序后数组为 [1, 1, 2, 2, 3, 3]。第一步 x 1堆为空压入 (1, 1)堆变成 {(1,1)}。 第二步 x 1堆顶 last 1x - 1 01 不小于 0且 last 1 不等于 0所以开新组压入 (1,1)。此时堆为 {(1,1), (1,1)}。 第三步 x 2堆顶是 (1,1)last 1 等于 x - 1弹出并压入 (2,2)。堆变成 {(1,1), (2,2)}。 第四步 x 2堆顶还是 (1,1)last 1 等于 x - 1弹出并压入 (2,2)。堆变成 {(2,2), (2,2)}。 第五步 x 3堆顶是 (2,2)last 2 等于 x - 1弹出并压入 (3,3)。堆变成 {(2,2), (3,3)}。 第六步 x 3堆顶是 (2,2)last 2 等于 x - 1弹出并压入 (3,3)。堆变成 {(3,3), (3,3)}。最终取 min答案是 3。和预期完全一致两个组分别都是 3 人。4.2 带失效组的样例1 2 100 101再看一组数字差距很大的情况。排序后为 [1, 2, 100, 101]。x 1开新组 (1,1)。 x 2堆顶 (1,1) 满足 last x - 1弹出并压入 (2,2)。 x 100堆顶是 (2,2)x - 1 992 99说明 {1,2} 这个组已经彻底封口弹出。此时堆空没有能接 100 的组开新组 (100,1)。 x 101堆顶 (100,1)last 100 101 - 1弹出并压入 (101,2)。最终堆里是 (101,2)答案 2。也就是说1、2 成一组100、101 成一组每组 2 人这是最优解。如果把 100 硬塞给上一组那组就变成 {1,2,100}显然不合法。4.3 时间复杂度与空间复杂度排序需要 O(n log n)。每个数字最多进堆一次、出堆一次每次堆操作都是 O(log m)其中 m 是当前组数m 一定小于等于 n所以整个处理过程也是 O(n log n)。空间上只用了堆和原始数组最坏情况下每个数字单独一组堆里同时存在 n 个元素空间复杂度 O(n)。这个复杂度在 n 为 10^5 甚至 10^6 时都能轻松通过。记住一个结论排序加优先队列几乎就是这类“动态维护多个候选序列”问题的标准答案。5. 常见问题与排查技巧实录5.1 我踩过的四个坑写这道题时我先后犯了四个错误每个都花了不少时间才定位。第一个就是 while 条件写成 x导致末尾为 x - 1 的组被误弹出。这个问题最隐蔽因为小数据可能碰巧不触发换成我上面给的样例 1 2 3 3 4 就立刻暴露。第二个错误是优先队列排序规则写反先比较人数再比较末尾值。这样做会让堆顶被一个“人数最少但末尾值落后很多”的组占据而真正能接住 x 的组可能埋在堆深处导致程序频繁开新组最短组答案偏小。第三个错误是修改堆顶。我第一次想图省事直接对pq.top()操作编译可以通过但运行结果完全不对。后来才意识到优先队列的内部结构不允许原地修改元素所有更新都必须 pop 出来再 push 回去。第四个错误是答案初始化。我一开始把 ans 初始化为 0然后循环里取 min结果不管怎么跑答案都是 0。这个错误很低级但也提醒我写这类“统计最小值”的代码时一定要想清楚初始值会不会干扰结果。5.2 常见问题速查表为了方便围观我把容易出问题的点整理成一个表刷题卡住的时候对着查一遍很快。现象可能原因解决办法答案一直偏小优先队列排序规则写反确认 first 是末尾值且 first 优先答案一直偏大弹出条件写成了 x改成 x - 1短组人数总是 1没有优先接人数少的组检查 pair 的比较逻辑是否同时比较 cnt修改堆顶后结果错乱原地改了 top() 的值先 pop 再 push越界或未知报错没考虑空堆直接访问 top()访问前先判空答案输出 0ans 初始值设置成了 0初始化为 n 或 INT_MAX5.3 用对拍验证你的贪心如果实在不放心贪心策略的正确性最笨也最有效的方法是写一个暴力程序生成 n 很小的随机数据把所有分组方案都枚举一遍然后和贪心程序对比。比如 n 不超过 8 时可以递归枚举每个数分到哪个组剪枝后跑得非常快。我第一次做这道题时就是用暴力对拍才确认了自己的 pop 条件写错。对拍脚本的思路很简单先写一个solve()函数跑贪心再写一个brute()函数跑暴力主程序里循环生成随机数组两个结果不一样就输出数据。这个习惯我一直保留到现在它比任何调试器都直接。6. 延伸思考这类“动态候选贪心”还能怎么用6.1 把模型抽象出来P4447 的本质是一个“在线决策”模型数据一个一个过来每个数据必须立即决定归属候选对象有多个且状态会动态变化。这种模型在竞赛题里非常常见。比如合并果子每次都要选两个最小的堆合并也是用一个优先队列维护当前所有堆的最小值再比如一些“调度问题”任务按时间到达要决定放到哪个机器上执行同样可以抽象成本题的结构。一旦你意识到“维护多路候选状态每次取最优”是这类题目的通用解法刷题效率会有明显提升。优先队列不是某个题目的专属技巧而是一把能开很多锁的钥匙。6.2 从这道题延展出去的练习方向如果要继续加深印象我建议把洛谷 P1090 合并果子、P2168 荷马史诗这类“哈夫曼树变种”拿来做对比它们都是堆的经典应用。还可以试试 P4053 建筑抢修这题也是贪心加堆但决策顺序不太一样能帮你把“什么时候该后悔、什么时候该替换”想明白。做完这些再回头看 P4447你会发现它只是把“堆里存的是什么”换了一下从“合并代价”换成了“组的末尾值和人数”整体框架并没有变。竞赛里很多题都是这样算法模板是旧朋友只是换了个场景重新认识而已。6.3 给新手的几点经验第一不要急着看题解。拿到这种“分组”“分配”类题目先在草稿纸上把样例推到第二步强迫自己说出“当前数字 x 有几种选择”。第二写代码之前先把堆里存什么、比较规则是什么写在注释里能避免一半的低级错误。第三AC 之后不要马上走试着改一个条件比如把x - 1改成x 1再想想答案会怎么变这样能把一道题吃得更透。我个人在实际操作中最深的体会是PA 的题目往往不是在惩罚你不会高级数据结构而是在考验你能不能把题意转成一个“每次都能做局部最优决策”的过程。P4447 这个“连续分组”的约束天然适合从小到大处理数字而“最短组最大”的目标又逼着你在多个可接组之间选择人数最少的那个。可以这么说这题是理解“贪心 优先队列”这一套组合拳的最佳入门题之一。如果你现在正被它卡住按照上面的思路手动推两个样例再把代码敲一遍我相信你很快就能把它稳稳收进自己的 AC 列表里。