每年 CSP-J 复赛一结束总能看到一批第一次参赛的同学在考场外拍大腿第一题居然耗了四十分钟最后还没拿满。我平时带备赛班最深的感受就是大家习惯性把“第一题”当成“送分题”看到题目背景是分糖果、做游戏就开始轻敌。实际上CSP-J 第一题考的是基础算法里出现频率最高的两类——模拟和贪心题目确实不难但越简单的题越容易因为读题不细、边界不清、代码不熟而翻车。今天要聊的这道“贪心的小朋友”就是一道仿照 CSP-J 第一题风格编写的模拟练习题背景是分糖果核心是贪心难度正好卡在入门组 T1 到 T2 之间。这篇文章适合正在备赛 CSP-J 的同学也适合刚接触贪心算法、想知道“贪心到底在贪什么”的初学者。我会从题目设定、正确性证明、代码落地到常见踩坑完整过一遍。1. 从“第一题”说起CSP-J 签到题的出题逻辑1.1 第一题真的只是“签到”吗很多同学对 CSP-J 第一题的印象就是“白给”实际刷过历年真题就会发现第一题虽然算法不难但坑点往往藏在读题和数据范围里。比如有的年份第一题是纯模拟循环加条件判断就够有的年份第一题是简单数学要分类讨论也有的年份第一题就是贪心排序后扫一遍。出题人会在题目背景上玩出各种花样但底层方法就那么几种模拟、枚举、简单贪心、基础数学偶尔会用到前缀和这类小技巧。第一题的定位是“让大部分认真备赛的同学拿分”不是“让零基础的同学也能靠常识做出来”。所以它真正考察的不是算法复杂度而是三件事读题速度快、代码实现稳、边界条件全。一场复赛 3.5 小时做四道题第一题如果能在 20 分钟内稳稳拿到 100 分后面三道题才会比较从容。如果第一题卡了半小时以上后面心理压力会很大。所以我训练学生的时候一直强调“第一题必须练到形成肌肉记忆”。1.2 模拟题“贪心的小朋友”到底长什么样为了保证讨论具体我先给出这道模拟题的完整设定。题目背景是分糖果这算.info CSP-J 题目里特别常见的场景因为贴近生活小朋友都能看懂。题目名称贪心的小朋友儿童节到了花花老师准备了 m 颗糖果打算分给班上的 n 个小朋友。第 i 个小朋友只在乎自己有没有拿到足够多的糖果如果分给他至少 a_i 颗糖果他就会很高兴如果少一颗他就不高兴。糖果只能整颗分每个小朋友可以拿 0 颗一颗糖果也只能分给一个小朋友。花花老师希望让尽量多的小朋友高兴而且她自己也想吃几颗所以不要求把手里的 m 颗全部分完。请问花花老师最多能让多少个小朋友高兴输入格式第一行两个整数 n 和 m分别表示小朋友数量和糖果总数。第二行有 n 个整数 a_1, a_2, ..., a_n表示每个小朋友开心所需的最少糖果数。输出格式一行一个整数表示最多能高兴的小朋友数量。数据范围1 ≤ n ≤ 10^50 ≤ m ≤ 10^91 ≤ a_i ≤ 10^9样例输入 15 10 2 3 5 8 12样例输出 13样例输入 23 0 1 1 1样例输出 20这个数据范围是故意设计的n 到十万m 和 a_i 到十亿。十万这个规模直接告诉我们别想用 O(n^2) 的方法排序加一次扫描是标答而十亿这个规模则提醒我们累加糖果数很可能超过 int 上限必须用 long long。这两个点都是实际竞赛里最常见的隐藏信息等会儿写代码的时候还要展开。2. 题目定位这道题到底在考什么2.1 从样例手动模拟理解“贪”在哪先拿样例 1 手动跑一遍。五个小朋友需要的糖果分别是 2、3、5、8、12老师手里有 10 颗。如果按输入顺序发先给第一个 2 颗能高兴再给第二个 3 颗累计用了 5 颗能高兴再给第三个 5 颗累计用了 10 颗正好高兴再给第四个 8 颗就变成 18 颗了超出 10 颗发不起。所以按原顺序最多让 3 个小朋友高兴。但这里有个很容易忽略的问题如果不排序而是按输入顺序扫描一旦遇到一个需求很大的小朋友可能把糖果全耗光了后面需求小的小朋友反而没机会。比如把样例改成4 6 5 1 1 5不排序直接扫第一个小朋友就要 5 颗剩下 1 颗只能再供一个需求为 1 的小朋友答案是 2。但如果先排序成 1、1、5、5那么 112 颗先满足两个再花 5 颗满足第三个虽然 257 6做不到所以答案还是 2。这个例子答案刚好一样不够震撼。再换一组4 6 5 2 2 2不排序直接扫5 颗给第一个剩 1 颗谁也满足不了答案 1。先排序变成 2、2、2、52226正好让 3 个小朋友高兴答案是 3。这个对比就非常明显了——顺序决定了前面的“大胃口”会不会堵住后面的“小胃口”。所以“贪心的小朋友”这个题名其实有两层意思题里的小朋友贪心做题的我们也要“贪”——每次都优先满足需求最小的小朋友追求数量最大化。2.2 题目真正考察的基本功有哪些这道题表面上是排序加循环实际考察了四个基本功。第一读题能力。“不要求把糖全部分完”这句话是题目的灵魂。如果理解成必须用完 m 颗有人就会想复杂了什么剩余糖果怎么处理之类的问题。实际上只要还有剩余糖就继续尝试不够分就停完全不用管最后剩了几颗。第二排序意识。排序是现代算法竞赛里最基础也最常用的预处理手段。很多贪心策略都建立在一个有序的序列上比如按需求从小到大按截止时间从小到大按价值从大到小。看到题就应该条件反射地想这个数据要不要排个序再处理第三线性扫描与提前终止。排序后累计需求一旦发现 current a[i] m后面的需求只会更大不可能满足直接退出循环即可。这个 break 是降低无用计算的关键虽然时间复杂度已经 O(n log n)但 break 在平均情况下能减少很大一半遍历。第四数据类型敏感。a_i 和 m 都是十亿级别n 是十万级别所有需求加起来可能到 10^14不用 long long 必炸。这个属于比赛里的经典送命点很多人样例过了提交却 WA原因就是 int 溢出。2.3 复杂度分析为什么这是标准 T1 解法排序用快速排序或者 C 标准库里的 sort时间复杂度 O(n log n)。排序后一次 for 循环扫描最坏扫满 n 个时间复杂度 O(n)。整体复杂度 O(n log n)。n 10^5 时log2(10^5) 大约 1710^5 × 17 也就是百万级别的操作在 CSP-J 的评测机上一秒以内绝对跑完。空间上只开了一个存需求值的数组O(n)。如果不用排序用计数排序思维呢因为 a_i 的范围到 10^9开不下这么大的桶所以标准解法就是排序而不是桶排序。这也是为什么数据范围里给的是 10^9而不是 10^6——出题人故意把排序做法设为预期解。3. 贪心策略的正确性为什么“按需排序”就是最优解3.1 直观理解把每个小朋友看成“开销”学贪心算法最怕的就是只知道背结论不知道结论怎么来的。这道题的贪心策略非常典型值得把正确性证明完整走一遍。将每个小朋友看作一个“待选购的商品”想让他开心就得付出 a_i 颗糖果的代价。目标是“花同样的预算买到尽可能多的商品”那直觉当然是从最便宜的开始买。一件商品 2 元一件商品 12 元手里只有 10 元能买哪件是个人都知道先买 2 元的。所以排序后从小到大发本质上是一个“成本最小优先”的策略。这个直觉每个人都能想到但竞赛里光有直觉不够还要能证明它一定最优。3.2 用交换论证给出严格证明假设原数组排序后得到 b_1 ≤ b_2 ≤ ... ≤ b_n也就是说 b_1 是最小需求b_n 是最大需求。按排序后的顺序依次累加发得起就发直到某一步发不起为止。这样得到答案 ans。现在要证明不存在任何其他方案能让超过 ans 个小朋友高兴。用反证法。假设存在一个更优方案能让 k ans 个小朋友高兴。由于任意方案中x 个小朋友被满足至少需要消耗这 x 个小朋友的需求值之和那么多糖果。那么在这 k 个小朋友里选出他们各自的需求值这 k 个值的总和一定不超过 m。注意关键点整个数组里最小的 k 个需求值之和一定不大于任意 k 个需求值之和。因为最小的 k 个值已经是所有组合里总和最小的了。而我们的贪心方案如果能做到 ans 个当尝试到 ans1 个时累加失败说明“最小的 ans1 个需求之和超过 m”。那么任意 ans1 个需求之和都不小于“最小的 ans1 个需求之和”也必然超过 m。这直接和假设矛盾——不存在任何能同时满足 ans1 个小朋友的方案。所以贪心得到的 ans 就是最大值。这个证明的核心是“前 k 小之和”这个单调性质也是这类资源分配贪心的通用证明套路。理解这个套路之后很多题的正确性证明都能往这个框架上套。3.3 这个贪心什么时候会失效弄懂“为什么对”也要知道“什么时候不对”这样以后遇到变体才不会死套模板。这道题之所以能贪心是因为所有小朋友彼此独立满足 A 不会影响满足 B每个小朋友带给老师的“收益”相同都是“多一个高兴的人”。一旦条件松动这个策略就会失效。举个例子如果每个小朋友除了要求 a_i 颗糖果之外如果他高兴了还会再帮老师带一个他的好朋友相当于“附带收益”这时候选择谁先被满足就不再只看需求大小了。又比如如果目标是让小朋友的“高兴程度总和”最大而不同小朋友高兴后带来的快乐值不同那么单纯按需求排序就不是最优可能需要按“快乐值除以需求值”的性价比来排这就变成分数背包的思路了。所以使用贪心之前一定先问自己三个问题决策之间会不会互相影响目标函数是数量还是权值资源能不能分割想清楚这三个问题才算是真正会做贪心题。4. 代码落地从伪代码到可提交的 C 程序4.1 写代码前先决定类型和变量先看类型。n 最大 10^5用 int 没问题。但 m 最大 10^9a_i 最大 10^9累计 used 最多可能是 10^5 × 10^9 10^14这远远超出 int 的 2^31 - 1约 2.1×10^9所以 m 和 used 必须开 long long。a_i 本身虽然不超过 10^9但参与加法时也建议直接用 long long 数组省得运算时类型提升不统一。再看变量。需要一个数组存需求值一个 long long 存总糖果数一个 long long 存当前已用糖果数一个 int 存答案。循环变量用 int 即可。4.2 一个容易忽略的小优化提前 break代码逻辑很简单排序然后遍历能发就发不能发就 break。这里的 break 不是可有可无的。因为数组已经有序如果当前的 a[i] 都加不进去了后面所有 a[j]j i都大于等于 a[i]更加加不进去再往下循环毫无意义。虽然这题的 O(n log n) 排序已经是复杂度瓶颈遍历的 O(n) 本来就是可接受的但 break 能让程序在数据较大时提前结束而且逻辑也更清晰地表达出“已经发不起任何人了”的状态。4.3 完整参考代码C17#include bits/stdc.h using namespace std; const int MAXN 100005; long long a[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long m; cin n m; for (int i 1; i n; i) { cin a[i]; } sort(a 1, a n 1); long long used 0; int ans 0; for (int i 1; i n; i) { if (used a[i] m) { used a[i]; ans; } else { break; } } cout ans \n; return 0; }这段代码里有一个很容易被新手忽视的细节数组 a 直接开成 long long。虽然每个 a_i 单独看不超过 1e9但 used a[i] 计算时如果 a 是 int就会发生 int 加 long long 的运算语法上没问题因为编译器会做类型提升但为了统一规范、避免自己写混干脆全程 long long 更省心。把using namespace std;和#include bits/stdc.h放在一起是竞赛里最常见的写法。有的同学平时写工程代码习惯用#include iostream、#include algorithm这当然也可以但比赛时用万能头其实更省时间而且 CSP 允许使用。平时刷题用哪个看个人习惯建议比赛直接上万能头。4.4 再给一份 Python 参考便于理解思路如果你平时用 Python 写算法题或者想更直观地看清楚算法流程可以看这个版本def solve(): import sys input sys.stdin.readline n, m map(int, input().split()) a list(map(int, input().split())) a.sort() used 0 ans 0 for x in a: if used x m: used x ans 1 else: break print(ans) if __name__ __main__: solve()Python 和 C 的逻辑一模一样读入、排序、扫描、输出。C 的优势在常数和运行速度Python 的优势在写起来快。备赛 CSP-J 建议主攻 C因为正式比赛的环境下 C 是适用范围最广的而且可以避免 Python 在极端数据下超时的问题。Python 只作为理解算法的辅助工具来用。4.5 多测几组边界数据验证代码写完代码别急着提交自己先造几组数据测试。我列几个经常用到的测试场景测试场景输入期望输出为什么测它最少人数1 5下一行31n 的下界验证基本流程没有糖果3 0下一行1 1 10m 的下界验证 used 初始为 0 的判断糖果足够2 100下一行1 992所有小朋友都能满足答案应为 n需求量全部相同4 10下一行3 3 3 33可以数几个 3 加起来不超过 10结果应该是 3刚好卡在边界3 6下一行2 2 23used 累加到刚好等于 m必须能用等号最大值溢出场景按最大范围构造正确计算验证 long long 是否真能接住大数“刚好卡在边界”那一组特别值得注意。如果代码里把 m写成 m这组数据会输出 2而正确答案是 3。这种差之毫厘的边界问题是评测时最冤枉的丢分点。5. 踩坑实录我在讲这道题时见到的典型错误5.1 错误一不排序直接遍历样例可能还真能过这是最常见的错误。有同学想“那我直接遍历边遍历边累加遇到加不进去就跳过或者直接停止”。如果遇到“前面的需求恰好都小”的样例这种写法也能过。但遇到刚才那组4 6和5 2 2 2的数据不排序的写法就会从正确答案 3 变成 1 或者 2。为什么大家会犯这个错因为很多第一题的“模拟”风格确实不需要预处理直接按题目顺序模拟就能过。但这题明确是贪心贪心的第一步往往是排序不是从头扫到尾。所以读题之后要先判断题型如果每个单位之间有“顺序优势”那可能要保持原顺序如果是“选谁都能得到同样收益只看代价”那大概率要排序。怎么避免养成一个习惯拿到题先问自己“这些小朋友的输入顺序有意义吗”如果顺序对答案没有影响那就大胆排序。读题时如果看到“任意顺序”“不要求”基本就是在暗示排序。5.2 错误二不等号方向写反if (used a[i] m)写成if (used a[i] m)或者反过来写成。这种错误在样例较小的时候很难发现因为大多数手工造的数据不会卡在“等于”的边界上。等评测机上一跑一个点 WA查半天都查不出来。排查方法很简单看到不等号立刻下意识地构造一组“刚好相等”的数据跑一遍。比如3 6、2 2 2正确答案应该是 3。只要用了就能过用了就会输出 2。把这类边界测试变成习惯比事后肉眼审查代码高效得多。5.3 错误三int 溢出小数据全对大数据全挂这种错误最有迷惑性。小样例跑得飞起一交上去 WA 一大片但又不是全 WA总有几个点能过。这种时候就要怀疑数据类型了。m 和 a_i 的上限都是 10^9n 是 10^5used 最大能累计到 10^14。如果你开的是 intused a[i] 在极端数据下会溢出成负数判断used a[i] m自然混乱。怎么快速发现看数据范围里最大的数乘起来超不超过 2^31。10^9 × 10^5 10^14远远超过必须 long long。给学生的建议是只要题目里任何数值上限超过 10^9或者两个变量相乘可能超过 10^9就直接无脑 long long。与其反复思考会不会溢出不如全用 long long反正比赛内存够用别在这种地方丢分。5.4 错误四不会自测样例过了就交很多初学者最大的问题不是不会写代码而是写完不知道对错。样例只是出题人给的“最小验证集”远远不完整。我建议每道题都学会一个朴素的对拍方法先写一个非常暴力的版本比如这题可以用 DFS 枚举所有子集计算最多能同时满足多少人然后随机生成小数据把暴力结果和贪心结果对比。数据范围放大到生成 8 到 10 个小朋友、随机 m 和 a_i只要几百组随机数据全部一致基本可以断定算法实现无误。这里给出一个简短的 Python 暴力验证思路方便理解from itertools import combinations def brute(a, m): n len(a) best 0 # 枚举所有子集看哪一个子集的需求总和不超过 m for r in range(n, 0, -1): for comb in combinations(range(n), r): if sum(a[i] for i in comb) m: return r # 从大往小找第一个找到的就是最大 return 0当然比赛时没时间写这么完整的对拍但至少可以针对边界手动造几组数据。记住一句话“样例过了不代表代码对边界过了才有资格提交。”5.5 竞赛节奏第一题应该怎么安排时间练这道题的时候我会给学生定一个硬性时间预算读题加建模不超过 5 分钟写代码加自测不超过 15 分钟总共 20 分钟内搞定。模拟考试时如果 20 分钟还没完全搞定就先跳过做后面的题最后再回来。不要因为第一题心态炸裂导致后面三道大题全崩。平时练习要有意识地掐表养成“先保 T1 再攻 T2/T3/T4”的比赛策略。6. 一道题带出的一串题贪心的常见套路与延伸6.1 和真题“分糖果”放在一起看差别在哪里很多同学在看历年题时都见过 2021 年 CSP-J 第一题“分糖果”那也是分糖果背景。一对比就会发现背景完全一样考法却完全不同。为方便识别我列个对比表对比维度2021 真题“分糖果”本文模拟题“贪心的小朋友”核心考点数学分类讨论 / 取模问题排序 贪心需要的基本操作判断 L、R 是否在同一段排序后线性扫描算法复杂度O(1)O(n log n)数据范围风格n 大但 L、R 也大n 最大 10^5值最大 10^9主要陷阱边界分类考虑不全漏排序、int 溢出这提醒我们比赛里不能看到“分糖果”三个字就套公式必须认真读题搞清楚它考的是数学、模拟还是贪心。相似的背景完全可能指向不同的解法。这也是为什么我一直强调“读题永远先于套模板”。6.2 如果加大难度这道题会怎么变想深度理解这道题可以试着把它往多个方向变形每个方向其实都对应一种新的算法思想。第一个变形每个小朋友不只关心数量还关心“别人是否比自己少”也就是互相比较。这时问题变成排队论式的分配不再简单排序。第二个变形每个小朋友的高兴程度不同有的小孩开心值 10有的开心值 1手里糖果有限目标是最大总开心值。这种带价值的变体如果需求可以取部分是分数背包按性价比排序如果必须全给或者全不给就变成 0-1 背包贪心就失效了得用动态规划。第三个变形如果第 i 个小朋友被满足后第 i1 个小朋友的需求会减少一半那么决策之间就产生了依赖需要换一种建模方式。第四个变形把“分糖果”换成“排队接水”每个人有接水时间问最小平均等待时间。这就变成经典的“短作业优先”贪心核心还是排序但目标变成了最小化等待时间总和。从这个角度看这道简单的模拟题其实是很多贪心题的“胚胎”吃透它的正确性证明思路以后遇到类似问题就能举一反三。6.3 另一种经典贪心以“跳跃游戏 II”为代表的区间扩展型有同学问贪心是不是就是排序加扫描其实贪心分很多种排序加扫描只是最常见的一种“资源分配型”贪心。另一种非常经典的是“区间扩展型”贪心典型题目就是跳跃游戏 II。那种题里不排序而是在每一步贪心地选择当前能跳到的最远位置不断更新可覆盖区间的右边界直到到达终点。核心思想和这道分糖果题完全不一样但底层的直觉是一致的每一步都做局部最优选择并证明这种局部最优不会破坏全局最优。备赛时建议大家按“贪心训练清单”来刷题先练排序型贪心再练区间型贪心再练区间调度、哈夫曼编码等进阶贪心。每道题做完后都要问自己两个问题这个贪心为什么正确交换论证还是反证法写得出证明这道题才算真正掌握了。6.4 给备赛同学的三条具体建议结合我带学生的经验最后整理三条建议直接照着做就行。第一条把贪心证明变成习惯。每次做完一道贪心题花五分钟写出“为什么局部最优就是全局最优”。写不出来的话说明还没吃透回去重做。能写出证明的题过一个月依然会做只背结论的题过一周就忘得干干净净。第二条用对拍积累边界敏感度。自己写题时多写一个暴力函数去对拍能快速发现排序漏了、边界错误、类型溢出这些问题。对拍脚本可以提前准备好比赛前如果允许带一个模板能省不少时间。第三条把第一题当成“保分题”来训练。平时练习时直接给自己 20 分钟限时做完立刻对拍错了分析原因。坚持一个月你就能明显感觉到第一题不再慌后面的题也有更多时间思考。我个人带备赛时最喜欢用这类“排序 扫描”的题让学生做限时训练因为它足够基础能暴露很多问题同时又能延伸到非常多的变体。这道“贪心的小朋友”建议你不管用什么语言都亲手写一遍、证明一遍、变形一遍。三道工序走完这一题你就真正吃透了。