1. 题目到底在问什么先别急着写代码P4447 这题我第一次看是在洛谷的 AH OI 2018 初中组题单里标题就俩字分组。题面很简短大意是给 n 个队员的能力值要求把队员分成若干组每组内队员的能力值必须是连续的也就是说组里任意相邻两个队员的能力值之差恰好是 1。比如能力值 3、4、5 能在一组3、5 就不能直接放一组因为中间缺了 4。现在要你最大化“人数最少的那一组”的人数输出这个人数。这道题乍一看很温和n 的范围我记得是 1e5 级别能力值可以到 1e9所以值域数组这条路直接被堵死。你如果按“能分就分能不分就不分”的直觉去贪大概率会栽。我在群里见过不少人拿到这题第一反应是排序后从头到尾扫一遍碰到断档就新开一组跑完样例发现也对交上去连 WA 好几发都找不到原因原因在于这种贪心实际上把“让最小组成员数尽量大”这个目标给丢了。我个人的习惯是拿到题目先做三件事确认输入规模、确认输出目标、确认限制条件里有哪些是“陷阱”。这题的陷阱至少有俩一是能力值范围大不能开数组二是“尽量大”这种最值目标背后往往藏着需要证明的贪心策略不是一眼扫出来的。下面我分成几个部分把思路推导、代码落地和踩坑记录都摊开讲。2. 错误思路复盘为什么排序连续段不可行先说一个非常自然的想法。既然每组要连续那我先排序然后遇到 a[i] 和当前组末尾相等就继续往下找 a[i]1、a[i]2直到断档然后把这一串当成一组。这种“拉最长连续段”的做法在很多区间覆盖题里都有用但这题不行。举个例子能力值是5 1 2 3 5 6按“拉最长连续段”来排序后从 1 开始找到 1、2、3断档于是第 1 组是 [1,2,3]再从 5 开始找到 5、6于是第 2 组是 [5,6]。最小组成员数是 2。这个结果看起来没错但如果数据换成8 1 2 3 4 4 5 6 7从 1 开始拉最长段能拉出 1、2、3、4然后遇到第二个 4落不了组内不能重复能力值断档第 1 组 [1,2,3,4]继续从第二个 4 开始拉出 4、5、6、7第 2 组 [4,5,6,7]。最小组成员数是 4。但最优分组呢应该是 [1,2,3,4,5,6,7] 和 [4]这样最小组成员数是 1更差。所以这种数据下连续段反而歪打正着。真正能暴露问题的数据是多组可接续但彼此争夺资源。比如6 1 1 2 2 3 3排序后是 1、1、2、2、3、3。如果你按“每人依次决定加入哪个组优先加入人数多的组”来贪处理第一个 1新开一组 A[1]处理第二个 1新开一组 B[1]处理第一个 2可以接 A、B。假如你为了“人多力量大”让 2 加入 A得到 A[1,2]、B[1]处理第二个 2能接的只有 BA末尾是2了再接2不行于是 B[1,2]处理两个 3分别接 A、B最终 A[1,2,3]、B[1,2,3]最小组成员数 3。这个策略碰巧最优。再来一个更阴间的7 1 2 2 3 3 4 4排序后 1、2、2、3、3、4、4。假设你每次把新数字接给“当前人数最多且可接的组”过程是1 开 A[1]第一个 2 接 AA[1,2]第二个 2 没得接开 B[2]第一个 3A 可接、B 可接选人数多的 AA[1,2,3]第二个 3 接 BB[2,3]两个 4 分别接 A、B得到 A[1,2,3,4]、B[2,3,4]最小组成员数 3。看起来还是好的。你有没有发现这么构造来构造去“优先接人数多的组”好像也能过问题出在人数相同的多个可接组上。如果当前可接的组有多个且人数一样接哪一个对后续影响很大。比如10 1 1 2 2 3 3 4 4 5 5开两个 1、两个 2、两个 3、两个 4、两个 5最后两组 [1,2,3,4,5]最小值 5怎么贪都是 5。这题刁钻的地方在于当你把多个“同一末尾能力值”的组放在一起时必须保证人数最小的那批组优先被增长否则会有人数很小的组滞留。比如数据6 1 1 2 2 2 3排序后 1、1、2、2、2、3。第一个 1 开 A[1]第二个 1 开 B[1]第一个 2 无论接 A 还是 B总有一个组停在 1第二个 2 只能接另一个于是两个组都变 [1,2]第三个 2 没得接开 C[2]最后一个 3能接的只有 C于是 C[2,3]。最终 A[1,2]、B[1,2]、C[2,3]最小组成员数 2。如果你在第三个“2”出现时强行让它接 A重复了不行或不开 C 而是把 A/B 拆了更差。这个例子里贪心必须严格保证“每次接人数最少的可接组”因为第三个 2 的出现是这种决策的关键。所以排序后连续段思路不是完全无效而是“拉最长段”和“优先接大组”都属于局部最优的直觉没触及这道题真正的最优子结构。要想稳妥解决必须把贪心策略上升到“能接就接、并且接人数最少的可接组”这个结论需要严格证明不能靠猜测。3. 正确贪心策略的推导与证明3.1 问题重新建模把每个组抽象成一个二元组 (末尾能力值 end, 组内人数 size)。初始没有组。现在按能力值从小到大逐个处理队员。对于当前队员能力值 x只有两种情况存在某个组的 end 恰好等于 x - 1这意味着 x 可以接到该组末尾。不存在这样的组那 x 只能新开一组end 为 xsize 为 1。目标是最小化所有组 size 的最小值。这个目标非常关键它决定了我们不能随意接组。思考一下如果有一种情况x 既可以接到 A 组也可以接到 B 组而 A 组人数比 B 组少我们应该接谁直觉上是接 A因为 A 更“弱”更需要增长。那这个直觉能不能严谨化可以用反证法。假设最优方案里把 x 接给了 B人数较多的组而 A人数较少的可接组没有被接。那么在最优方案里A 的 size 保持不变而 B 的 size 加 1。现在我们构造一个新方案把 x 从 B 中拿出来接到 A 上。A 的 size 增加 1B 的 size 减少 1。原本所有组 size 的最小值只可能来自 A、B 或其他组。如果最小值来自其他组两个方案最小值一样如果最小值来自 A新方案里 A 变大了最小值不会变差如果最小值来自 B新方案里 B 变小了似乎可能变差。这里要小心B 原本 size 较大即使减 1仍然大于等于 A 原来的 size而 A 加 1 后更大了。所以新的最小值不会比原方案小。这说明“接人数较少的组”永远不会比“接人数较多的组”差。再看“不接而新开一组”的情况。如果 x 明明可以接到某个组却新开一组那么新组 size 为 1最小值肯定被拉到 1除非原方案里已经有 size 为 1 的组否则这是致命的。即便原来已经有 size 为 1 的组新开一组也不会让最小值变大。所以“能接就接”一定不劣。于是得到完整贪心策略从能力值小到大处理对于每个 x如果存在末尾为 x-1 的组则一定有且仅有一个组需要被扩展扩展目标是其中 size 最小的那个如果不存在就新开一组。3.2 为什么不能直接开一个数组按值域记录能力值最大到 1e9直接开 int 数组肯定不行。很多人用 unordered_map 或 map 来当“桶”用key 是组的末尾能力值value 是“所有以该值结尾的组的人数集合”。由于每次要找某个 key 对应的最小 size所以这个集合需要是小根堆也就是 priority_queueint, vector , greater 。C 的 map 自带有序性查找 x-1 是 O(log m)m 是当前存在的不同末尾值数量完全可接受。用小根堆而不是 vector是因为 vector 找最小值是 O(size)如果很多人挂在同一个末尾值上最坏会退化到 O(n^2)。我之前看到有人用 vector 然后每次扫一遍找最小数据一大直接超时。优先队列的 top 是 O(1)pop 和 push 是 O(log size)整体复杂度能控住。3.3 复杂度分析排序 O(n log n)遍历每个能力值做一次 map 查找每次查找 O(log m)增删堆元素 O(log s)m 和 s 都受 n 限制因此整体 O(n log n)。对 1e5 的数据量来说非常轻松实测排序反而是主要耗时。4. 两种可实现写法详解4.1 写法一map priority_queue 存组的末尾和人数这是最标准的写法我在本地跑了很多随机数据稳定通过。直接贴代码关键逐行解释#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); // key: 组末尾的能力值 // value: 所有以 key 结尾的组的人数用小根堆维护方便取最小的那个组 mapint, priority_queueint, vectorint, greaterint mp; for (int x : a) { auto it mp.find(x - 1); if (it ! mp.end() !it-second.empty()) { // 取出人数最少的可接组 int sz it-second.top(); it-second.pop(); mp[x].push(sz 1); // 如果该末尾值对应的组全部被扩展完清理掉避免后续误判 if (it-second.empty()) { mp.erase(it); } } else { // 没有可接组新开一组 mp[x].push(1); } } int ans INT_MAX; for (auto kv : mp) { while (!kv.second.empty()) { ans min(ans, kv.second.top()); kv.second.pop(); } } cout ans \n; return 0; }解释几个细节map.find(x - 1) 为什么能找到“可接组”因为我们按能力值升序处理能接 x 的组一定是之前某个队员形成的末尾能力值为 x-1。升序保证了 x-1 的所有组都已经存在于 map 中。为什么 x 可能同时对应多个组比如多个“1”出现时每个 1 都可能开一个独立组它们末尾都是 1。我把它们全部塞进 mp[1] 对应的小根堆。为什么要 erase 空 key因为 map 的 find 会命中 key 为 x-1 但对应堆已经空的条目。如果不清除后面的能力值 y (x-1)1也就是 x 本身再来一个时它 find 到 x-1 但堆为空处理逻辑会变成“新开一组”可能影响正确性。实际上我在本地测试时发现不清也不一定错但清除后语义更干净排查问题方便。4.2 写法二用数组模拟“每个末尾值的活跃组队列”map 的常数略大追求极限性能可以用“离散化 优先队列数组”。做法是先把所有能力值排序去重得到离散化后的下标然后每个下标挂一个小根堆。不过这题 n 只有 1e5map 完全够用我一般不会为了常数牺牲代码可读性。4.3 关于二分的旁门左道还有一部分人会想到二分答案 k然后判断能否让所有组人数至少为 k。判断函数里依然要用贪心而且贪心细节和原题几乎一样只是决策时多了“如果组人数到 k 就不再扩展”的限制。这个思路不是不行但一方面复杂度多一个 log另一方面二分边界的判定很容易把人绕晕。我见过不下三个同学写二分的 check 时把“优先扩展小组”和“人数满 k 就不再扩展”的优先级搞反样例过了但大数据 WA。所以我建议直接贪心一步到位。5. 手把手构造测试数据验证写竞赛代码最怕思路对、样例过、大数据错。这种贪心题尤其需要自己构造边界数据来验证光靠题目样例完全不够。我下面列几个我常用来验证这题的数据。第一个是重复能力值6 1 1 2 2 3 3跑一遍逻辑两个 1 各自开组即 mp[1] 里有 {1,1}第一个 2 找到 mp[1] 里最小的 1弹出mp[2] 推入 2第二个 2 再做一次mp[2] 推入 2两个 3 各扩展一次最后 mp[3] 里有 {3,3}答案 3。正确。第二个是断档导致新组5 1 2 3 5 61 开组2 接3 接mp[3] 有 {3}5 找不到 mp[4]只能开新组 mp[5] 有 {1}6 接mp[6] 有 {2}答案 2。口算正确。第三个容易错的7 1 1 2 2 3 3 4前面几个和刚才一样得到 mp[3] 有 {3,3}最后 4 出现时可接的是 mp[3]弹出最小 3得到 mp[4] 有 {4}。最终答案的候选是 4 和另一个 3答案 3。这里如果不能保证选最小而选了那个 3 原本可能是 3现在被 4 接走了就没导致问题。你会发现很多数据下接哪个似乎都差不多但数据量大时差异会累积然后爆炸。第四个是压力边界数据能力值从 1 到 n 连续排列比如 n 100000a[i] i。预测结果是一个组 100000 个人答案 100000。跑贪心第一个 1 开组后面 2 到 100000 全部接它最终 mp[100000] 有一组 size 100000答案 100000。没问题。第五个是极限分散比如 n 100000所有能力值都相同假设都是 1。预测结果是 100000 个组每组一个人答案 1。跑贪心每个 1 都开新组mp[1] 的堆里有 100000 个 1最后答案 1。这个测试能检验小根堆的存储与遍历也能发现如果你用 vector 每次找最小大概率会 TLE。6. 常见错误与排查技巧6.1 错误一能力值数组直接开 bool 或 int能力值范围 1e9开数组直接爆内存。我见过有人用vectorint cnt(1000000005)编译器直接给你一个 Memory Limit Exceeded。正确做法是用 map 或离散化。这个错误属实低级但考试时一紧张真有人写。进阶做法是先用 sort 去重再对每个能力值映射到下标但这题 map 足够。6.2 错误二用 vector 模拟堆每次找最小这个错误隐蔽性强。很多人会写成vectorint group[MAXV]然后每个 x 处理时遍历 group[x-1] 找最小复杂度在最坏情况下是 O(n * 组数)。能力值相同的极端数据会让一个 vector 里挂 n 个元素每次插入都遍历一遍直接卡成 O(n^2)。正确做法是用priority_queueint, vectorint, greaterint。这个坑在本地用小数据测不出来必须造大数据的极端重复值才能暴露。6.3 错误三统计答案时漏掉还在堆里的组有同学只在“新开一组”时更新答案或者在扩展时更新以为答案只会出现在这个时机。其实最终答案可能来自一个早已存在、一直没人接、最后也没被遍历到的组。比如能力值 1 出现一次后直接结束没有后续最终 ans 必须算上这个 size 为 1 的组。正确做法是最后遍历整个 map把每个堆里的元素都取出来取 min。6.4 错误四erase 空 key 用错方式C 里map.erase(it)之后it 就失效了不能再访问。如果你在循环里一边遍历 map 一边 erase很容易触发迭代器失效。我的写法里 erase 之后直接 break 或者 return避免继续使用 it。另外如果mp.find(x - 1)返回 end()你又直接访问it-second会 RE必须先判断 it 是否等于 end()。代码里我用了it ! mp.end() !it-second.empty()双重判断稳。6.5 错误五排序后没有判重就处理重复值排序本身没问题但有些选手会在排序后把相邻相同的值当成“同一个 x 只处理一次”于是跳过重复值。这会出大问题因为每个队员都是独立个体一个能力值可能对应多组操作。正确的循环是 for (int x : a) 一个接一个处理不能去重。6.6 调试技巧遇到 WA我推荐三件套多造小规模样例n 10能力值在 1 到 5 之间用暴力全排列或直接手算验证。对拍。写一个 O(2^n) 或 O(n!) 的暴力枚举所有分组方案n 小于等于 8 时和贪心输出对拍一旦不一致立刻缩小范围。输出中间状态。在扩展组时打印 x、取出的 sz、新推入的 sz肉眼观察是否总是取最小。我之前用对拍找到一个隐蔽 bug当 map[x-1] 里堆顶 size 和另一个组相同我随机选一个扩展结果答案偶尔不对。原因不是随机性而是我在 erase 空 key 后没有重新 find后续操作用了旧迭代器。对拍能精准暴露这种偶发问题强烈建议无论比赛还是平时练习都养成对拍习惯。7. 这题背后的思维迁移贪心决策的本质P4447 并不是一道孤立的题它的贪心结构在竞赛里非常经典按某个维度排序然后用一个能 O(log n) 维护最小值的结构每一步对“最需要被照顾的对象”做操作最终满足全局最值。类似题型包括合并果子每次取最小的两堆合并用小根堆维护。导弹拦截/最长上升子序列排序后每次接在某个序列尾部往往需要维护尾部最小值。若干调度问题按截止时间排序用小根堆或者 set 维护当前最优集合。核心模式是“能接就接接就接最弱的那个”。这个模式在证明时通常采用交换论证法如果最优解没有使用这个策略可以通过交换相邻两个决策使得结果不差直到变成贪心解。P4447 正好是教学级例子因为它的交换论证并不复杂适合拿来自我训练。如果题设稍微改动比如“最大化人数最多的组”或“让所有组人数尽量平均”贪心策略就会彻底变化。前者可能倾向于把所有元素串成一个大组后者可能需要优先补小组。这种变式非常适合作为小组讨论题能帮助你把问题模型吃透。我对后来人的建议是不要把 P4447 当成一道“会了就完了”的题而是去体会从反例到证明再到数据结构落地的完整过程。尤其是“为什么能接就接”这条你自己独立证明一遍比看十篇题解都有用。竞赛里很多题看起来是考数据结构实际考的是你能不能从直觉里提炼出可证明的贪心命题。这题就是那道分界线跨过去你的贪心题感会明显提升一个台阶。