上周末给训练队的孩子做了一套CSP-J复赛模拟卷打开第一题我就笑了——题目叫“贪心的小朋友”。题面不长、样例友好看起来就是标准的送分题但批改完发现AC率只有六成出头。问题基本都出在最基础的东西上数据范围没看、贪心方向想反、样例过了就没测边界。这篇就把这道题从头拆到脚从题面到贪心证明再到代码细节和历年T1的考法一次讲透。正在备考CSP-J的同学或者刚接触贪心算法、想搞懂“为什么这题能贪心”的读者可以直接照着这个思路过一遍。1. 拿到题先别动手题目到底在考什么1.1 题面与样例速览这道模拟题的题面非常简单核心信息就几句话老师准备了 s 块糖果班上有 n 个小朋友。第 i 个小朋友想要 a[i] 块糖果。如果一个小朋友实际拿到的糖果数不少于他想要的块数这个小朋友就会很开心。现在问老师最多能让多少个小朋友开心输入格式是常规的两行第一行两个正整数 s 和 n第二行 n 个正整数 a[1] 到 a[n]表示每个小朋友想要的糖果数。样例给得也很克制输入10 4 6 2 3 5输出3样例解释很清楚先满足想要2块的小朋友剩8块再满足想要3块的剩5块最后满足想要5块的刚好花光。3个小朋友开心。如果一上来先满足想要6块的那个剩4块最多只能再满足2块或3块的小朋友最后只有2个开心。所以答案是3。这个手算过程看起来平凡但它恰恰是整道题的核心为什么从需求小的开始喂因为糖果总量固定想让数量最大化必须让每一份糖果都发挥最大价值。后面我会用反证法严格说明这一点。1.2 为什么CSP-J的T1会放一道“贪心排序”的题很多初学者对CSP-J第一题有误解觉得T1就是白给题随便模拟一下就能过。从近几年的真题看T1确实不难但已经不再是纯模拟的天下了。稍微回忆一下历年复赛T12020年是“优秀的拆分”考二进制拆分的理解2021年是“分糖果”本质是数学分类讨论加一点贪心思维2022年是“乘方”考快速幂或循环边界的控制2023年是“小苹果”表面是模拟取苹果实际要你找规律不能硬模拟2024年是“扑克牌”考集合去重和计数。你会发现T1的稳定主题是“简单算法思维”贪心、数学、模拟各占一部分而贪心因为代码极短、坑点藏在思维里特别适合当第一题。这道“贪心的小朋友”就是典型代表。代码量不到20行算法一句话讲完排序后从小到大满足。但能不能想到这一点、敢不敢证明“从小到大一定对”决定了你是花5分钟AC还是花30分钟反复怀疑人生。所以别嫌题简单T1真正的考试目标不是算法而是你有没有把基础吃透。1.3 我拿到题后会先做的三件事很多孩子做题第一反应是打开编译器写代码这不是好习惯。我拿到这道题会先做三件事这三件事对任何CSP-J T1都适用。第一件事读数据范围。看到 1≤n≤10^5、1≤s≤10^9、1≤a[i]≤10^9我立刻意识到两件事一是 O(n^2) 的算法不可能过必须 O(n log n) 或 O(n)二是 s 和 a[i] 都可能到十亿涉及累加时必须用 long long。这两个判断不做后面必然出事。第二件事手算样例。不是照着题目给的解释看一遍而是自己在草稿纸上演算。我会问自己如果我先满足6块的小朋友会怎样如果我先满足2块的呢通过对比算法的雏形就出来了——需求小的优先。第三件事确定算法复杂度是否可行。排序 O(n log n)总复杂度约 10^5 log 10^5在CSP-J的时间限制下非常宽裕。确认可行后再动手写代码。整个过程不超过两分钟但能避免绝大多数低级失误。2. 贪心策略为什么“先满足需求小的小朋友”一定正确2.1 用生活逻辑建立直觉贪心算法的名字听起来高大上核心就一句话每一步都做当前看起来最划算的选择并希望局部最优能堆积成全局最优。放到这道题里“当前最划算”是什么当然是先满足那个要糖果最少的小朋友。你可以把它想象成用有限的钱逛超市买零食每包零食价格不同你想买最多的包数。正常人都会先拿最便宜的几包拿到钱不够为止。这就是贪心。但生活直觉归直觉竞赛里必须给出严格证明否则换个数据可能就翻车。糖果题里的约束只有一个糖果总数固定。每个小朋友只需要一个数字 a[i] 来刻画需求没有重量、价值、优先级等额外维度。正是因为只有一个约束贪心才成立。如果再加一个“每个小朋友必须获得特定颜色的糖果”之类的条件问题就变复杂了。这也解释了为什么竞赛里很多贪心题都长这样单约束、代价可排序、目标是数量最大化。2.2 用反证法证明“从小到大选”的合理性证明方法有很多我推荐反证法加交换论证这是竞赛里最常用的手段。假设存在一个最优解它没有选某个需求更小的小朋友 p却选了需求更大的小朋友 q且 a[p] a[q]。现在我做一次交换把分配给 q 的糖果配额 a[q] 里的 a[p] 份分给 p同时从 p 那边挪走多出来的糖果。因为 a[p] a[q]分配给 p 之后还有剩余剩余糖果只会更多或不变而开心的人数保持不变。这说明了什么任何“跳过小需求、满足大需求”的解都能被改造成“大需求被替换成小需求且人数不劣”的解。反复做这种交换最终一定存在一个最优解满足的小朋友恰好是按需求从小到大依次选出来的。所以先排序再从小累加一定能得到全局最优。其实还可以更直观地理解糖果总量 s 是预算a[i] 是单价目标是购买数量最大化。既然每件商品只能买一次且没有其他限制最优策略当然是按单价从低到高买。排序后从前往后买买到买不起为止这不就和我钱包里的钱花在超市零食区的逻辑完全一致吗2.3 顺带说说什么时候贪心会失效每次讲完贪心总有学生会问是不是所有问题都能贪心当然不是。为了说明白我通常拿“01背包问题”做对比。假设你有一个背包容量10有三件物品A重量6价值8B重量5价值6C重量5价值6。如果按性价比贪心A的价值重量比是1.33B和C是1.2你会先选A然后剩余容量4什么都装不下总价值8。但最优解是选B和C总价值12。为什么贪心失效因为物品不可分割而且有两个维度的信息重量和价值需要统筹。回到糖果题为什么贪心就成立因为它只有一个维度——需求量 a[i]。所有小朋友没有附加价值每个人对总答案的贡献都是1且唯一区别就是代价不同。当目标是数量最大化时选最小代价总没错。这背后是一种很常用的贪心模型单约束下的最小代价覆盖。抓住这个模型以后只要看到“固定资源、单位收益为1、求最多能完成几个”的题第一反应就应该是排序贪心。3. 完整实现C代码与每一步的细节3.1 可以直接抄的满分代码代码非常短我直接贴完整版。这是我推荐在考场上写的形式思路清晰不容易出错。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long s; int n; cin s n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); int ans 0; for (int i 0; i n; i) { if (s a[i]) { s - a[i]; ans; } else { break; } } cout ans \n; return 0; }核心逻辑就三块读入、排序、从小到大累减并计数。很多同学写完后会有个疑问要不要把已经满足的小朋友从数组里删掉不需要。因为排序之后我们只需要从前往后遍历已经消耗的糖果通过变量 s 的减法体现数组本身不需要改动。这里没有任何复杂的数据结构vector 或者普通数组都能胜任如果你更习惯静态数组直接写成 long long a[100005] 也完全没问题。3.2 三个容易翻车的关键细节第一long long 不能省。看到 s 和 a[i] 的最大范围都是 10^9有的同学觉得 int 能存下就只开了 int。这确实能存下单个数但一旦在某个极端数据里把所有小朋友的 a[i] 加起来或者 s 在循环中反复减法中间结果完全可能超过 2^31-1。虽然这道题里单次判断 s a[i] 不会溢出但为了避免在类似题里踩坑我建议只要数据范围接近 10^9涉及累加、累减、乘积的变量一律开 long long。CSP-J 里这几乎是一条保命原则。第二排序方向别搞反。贪心策略是“需求小的优先”所以必须 sort(a.begin(), a.end()) 升序。有些同学写顺手了可能用了 greater ()结果代码逻辑没变却先满足需求最大的小朋友样例大概率跑不过。如果忘了 sort 的用法也可以写一个简单的 for 循环手动排序但没必要直接用 STL 的 sort 最稳。第三遇到第一个不能满足的就可以 break。因为数组已经升序排列如果当前 s 连 a[i] 都满足不了那后面的 a[i1] 更大更不可能满足。所以 else 分支里直接 break 退出循环不仅节省时间还让逻辑更清晰。有些同学不写 break继续让循环跑完结果会出现 s 变成负数、ans 却还算进去了的错误——虽然用 if 判断也能挡住但 break 才是这个场景下最干净的做法。3.3 复杂度分析为什么 O(n log n) 稳过排序的时间复杂度是 O(n log n)随后的遍历是 O(n)整体复杂度为 O(n log n)。在 n10^5 时排序操作大概做 10^5 乘以 16 次比较量级在百万级别任何评测机都能轻松承受。空间复杂度是 O(n)用来存 a 数组。如果 n 再大一点比如 10^6O(n log n) 仍然可行如果 n 到了 10^7排序可能就吃力了需要结合桶排序等思路优化。但CSP-J 的数据范围通常不会这么极端这道模拟题的设定是非常良心的。值得一提的是如果数据里 n 是 10^7 且 a[i] 范围很小也可以用计数排序做到 O(n maxA)但那属于进阶玩法T1 阶段没必要。4. 我批改时看到的高频错误与排查方法4.1 样例过了交上去却全WA这是第一次参赛的人最容易遇到的情况。样例过只能说明代码在样例上没有错不代表算法和边界没有问题。我让孩子们写完代码后做的第一件事就是自己构造几组特殊数据来验证。我常用的用例有这几类n1 且 s 刚好等于 a[0]n1 且 s 小于 a[0]s 非常大所有小朋友都能满足所有 a[i] 都相同a[i] 里有极端大的数。比如构造 s1, n1, a[0]1答案应该是1构造 s0 虽然题目范围可能不允许但加上判断也无妨构造 s1000000000, n100000, 所有 a[i]1000000000如果不开 long longs 减去 a[i] 后变成0看起来没问题但如果你用 int 去存总和或某个中间值大样例直接暴露输出可能为负数或者错误数字。另外我强烈建议初学者学一下“对拍”。写一个非常暴力的版本枚举所有小朋友子集计算出最多能满足几个再和贪心代码的结果比对随机生成小数据跑几百轮。小数据下暴力一定能跑出正确结果如果贪心结果和暴力一致说明贪心策略没问题。对拍脚本不需要复杂哪怕用几行 Python 也能做。这不光是验证这一道题的方法也是以后调试贪心题的通用思路。4.2 评测环境下的“鬼故事”CSP-J 复赛用的是 Linux 评测环境而很多选手平时在 Windows 的 Dev-C 里写代码。环境差异可能会带来一些奇奇怪怪的坑。最经典的就是 long long 的格式化输出。在 Windows 的 MinGW 环境下printf 输出 long long 有时候要用 %I64d而 Linux 下要用 %lld。如果格式串不对输出会很诡异。我的建议是统一用 cout 输出代码里加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr)效率也够格式问题完全不操心。其次要注意 freopen 重定向的使用CSP-J 复赛要求从文件读入、向文件输出考试时经常有人忘记写 freopen或者只写了输入没写输出结果本地能看到结果评测机全是0分。写完代码务必要检查主函数里有没有freopen(candy.in, r, stdin); freopen(candy.out, w, stdout);最后静态数组开小了会导致运行错误。如果题目给的 n 最大是 10^5我习惯把数组开到 100005 甚至 200005多留些余量。使用 vector 则完全不用操心这个问题所以我个人推荐入门阶段直接学 vector顺便树立“动态管理内存”的意识。4.3 常见问题速查表我整理了一张做题和批改过程中最高频的问题表方便大家自查。症状可能原因解决方案样例过、大样例全WA没开 long long累加溢出s、a[i]、累加变量全部用 long long输出结果比正确答案小排序方向写反先从大需求开始sort 默认升序不要加 greater循环结束后 s 变成负数没有 break继续处理后面的需求遇到 s a[i] 立刻 break本地能跑评测0分缺少 freopen 或文件名写错检查输入输出重定向和文件名运行错误静态数组开小了数组多开一些或用 vector输出格式问题使用 printf 格式化 long long 不当统一用 cout 输出这张表里的问题我几乎每年批改都能见到。它们都不难修但考试时任何一条都可能让T1丢分。第一题都不能稳稳拿下后面心态很容易崩。5. 从这道模拟题看历年CSP-J T1的命题规律5.1 历年复赛T1考点速览把近五年CSP-J复赛第一题放在一起看规律非常明显。年份题名核心考点难度特点2020优秀的拆分位运算、二进制思维判断奇偶后按位拆分2021分糖果数学分类讨论、贪心思想在区间内找余数最大化2022乘方快速幂、循环边界控制防溢出结果超限输出-12023小苹果模拟、取整规律不能硬模拟要发现每轮取走1/32024扑克牌集合去重、计数本质是统计不同花色点数从这张表可以看出来CSP-J 的T1并不考复杂数据结构但也不是无脑模拟。它更倾向于用一个非常简单的背景包装一个基础算法或数学结论考察你在紧张环境下能不能快速识别模型、准确处理边界。这道“贪心的小朋友”完美符合这个定位算法名字听起来很高大上实际就是排序后从小满足代码量极小。5.2 同款贪心模型的“变形题”怎么想历年真题里和“贪心的小朋友”最像的是2021年的“分糖果”。那题要求在区间 [L, R] 中选一个数 n最大化 n mod k 的值。很多人当时连题都读不懂其实思路也是贪心加分类讨论如果区间里存在 k 的倍数减1直接取那个值否则就取 R因为余数一定越大越好。你发现没有核心还是“在当前可选范围内做局部最优选择”。所以别小看T1它往往是一类题型的种子。还有一个经典贪心题叫“跳跃游戏2”问最少跳几次能跳到终点。每步能跳的距离是一个区间贪心策略是每次找当前区间内能延伸最远的那个位置。它和糖果题看起来完全不同但内在逻辑都是“每一步选局部最优并用证明排除后顾之忧”。如果你把“糖果题”吃透了再去看跳跃游戏2会发现贪心不是玄学而是一套能套用的思考方式先确定约束、再构建局部策略、最后用反证或交换论证验证。5.3 备考T1的三条实在建议结合这些年带队的经验我给备考CSP-J的同学三条具体建议。第一条T1控制在25分钟以内不要死磕。如果你在15分钟内还没思路大概率是模型识别出了问题先跳过做后面的题最后再回来看。一条路走到黑在比赛中是致命的。第二条平时做题别只追求AC。每做完一道题多问自己三个问题为什么这个算法对边界数据是什么如果数据范围扩大十倍还能不能过这三问能帮你把一道T1训练成三道题的效果。第三条多练“手算样例”的能力。很多人写代码飞快但演算能力差题目稍微变化就不知道代码在干什么。竞赛说到底拼的是思维准确性代码只是把思维落地的工具。手算样例能逼你真正理解题意而且一旦样例手算和代码输出不一致你能立刻定位是算法问题还是实现问题。我个人在实际训练中的习惯是每次模拟赛做完T1都会用对拍脚本把小数据暴力解和贪心解跑一遍确认没有边界问题后才算真正“拿下”这道题。因为T1太重要了它决定了整场比赛的心理状态。第一题稳稳AC后面的题你怎么写都有底气第一题翻车后面再简单也会疑神疑鬼。所以这套模拟卷我特意把“贪心的小朋友”放在第一题也是想让孩子们在比赛一开始就体会到CSP-J的第一道题不需要很炫的技巧它考验的是你愿不愿意静下心来读题、手算、证明再用干净利落的代码把它实现出来。把这个过程练成肌肉记忆你的CSP-J之路就稳了一大半。