企业官网建设流程全解析

每年 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^5
• 0 ≤ m ≤ 10^9
• 1 ≤ a_i ≤ 10^9

样例输入 1：

5 10 2 3 5 8 12

样例输出 1：

3

样例输入 2：

3 0 1 1 1

样例输出 2：

0

这个数据范围是故意设计的，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，那么 1+1=2 颗先满足两个，再花 5 颗满足第三个，虽然 2+5=7 > 6，做不到，所以答案还是 2。这个例子答案刚好一样，不够震撼。再换一组：

4 6 5 2 2 2

不排序直接扫：5 颗给第一个，剩 1 颗谁也满足不了，答案 1。先排序变成 2、2、2、5，2+2+2=6，正好让 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) 大约 17，10^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 个，当尝试到 ans+1 个时累加失败，说明“最小的 ans+1 个需求之和超过 m”。那么任意 ans+1 个需求之和都不小于“最小的 ans+1 个需求之和”，也必然超过 m。这直接和假设矛盾——不存在任何能同时满足 ans+1 个小朋友的方案。所以贪心得到的 ans 就是最大值。

这个证明的核心是“前 k 小之和”这个单调性质，也是这类资源分配贪心的通用证明套路。理解这个套路之后，很多题的正确性证明都能往这个框架上套。

3.3 这个贪心什么时候会失效

弄懂“为什么对”，也要知道“什么时候不对”，这样以后遇到变体才不会死套模板。这道题之所以能贪心，是因为所有小朋友彼此独立，满足 A 不会影响满足 B，每个小朋友带给老师的“收益”相同，都是“多一个高兴的人”。

一旦条件松动，这个策略就会失效。举个例子：如果每个小朋友除了要求 a_i 颗糖果之外，如果他高兴了还会再帮老师带一个他的好朋友，相当于“附带收益”，这时候选择谁先被满足就不再只看需求大小了。又比如，如果目标是让小朋友的“高兴程度总和”最大，而不同小朋友高兴后带来的快乐值不同，那么单纯按需求排序就不是最优，可能需要按“快乐值除以需求值”的性价比来排，这就变成分数背包的思路了。

所以使用贪心之前，一定先问自己三个问题：决策之间会不会互相影响？目标函数是数量还是权值？资源能不能分割？想清楚这三个问题，才算是真正会做贪心题。

4. 代码落地：从伪代码到可提交的 C++ 程序

4.1 写代码前先决定类型和变量

先看类型。n 最大 10^5，用 int 没问题。但 m 最大 10^9，a_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 完整参考代码（C++17）

#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 多测几组边界数据验证代码

写完代码别急着提交，自己先造几组数据测试。我列几个经常用到的测试场景：

“刚好卡在边界”那一组特别值得注意。如果代码里把<= 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^9，n 是 10^5，used 最大能累计到 10^14。如果你开的是 int，used + 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 第一题“分糖果”，那也是分糖果背景。一对比就会发现，背景完全一样，考法却完全不同。为方便识别，我列个对比表：

这提醒我们：比赛里不能看到“分糖果”三个字就套公式，必须认真读题，搞清楚它考的是数学、模拟还是贪心。相似的背景，完全可能指向不同的解法。这也是为什么我一直强调“读题永远先于套模板”。

6.2 如果加大难度，这道题会怎么变

想深度理解这道题，可以试着把它往多个方向变形，每个方向其实都对应一种新的算法思想。

第一个变形：每个小朋友不只关心数量，还关心“别人是否比自己少”，也就是互相比较。这时问题变成排队论式的分配，不再简单排序。

第二个变形：每个小朋友的高兴程度不同，有的小孩开心值 10，有的开心值 1，手里糖果有限，目标是最大总开心值。这种带价值的变体如果需求可以取部分，是分数背包，按性价比排序；如果必须全给或者全不给，就变成 0-1 背包，贪心就失效了，得用动态规划。

第三个变形：如果第 i 个小朋友被满足后，第 i+1 个小朋友的需求会减少一半，那么决策之间就产生了依赖，需要换一种建模方式。

第四个变形：把“分糖果”换成“排队接水”，每个人有接水时间，问最小平均等待时间。这就变成经典的“短作业优先”贪心，核心还是排序，但目标变成了最小化等待时间总和。

从这个角度看，这道简单的模拟题其实是很多贪心题的“胚胎”，吃透它的正确性证明思路，以后遇到类似问题就能举一反三。

6.3 另一种经典贪心：以“跳跃游戏 II”为代表的区间扩展型

有同学问，贪心是不是就是排序加扫描？其实贪心分很多种，排序加扫描只是最常见的一种“资源分配型”贪心。另一种非常经典的是“区间扩展型”贪心，典型题目就是跳跃游戏 II。那种题里不排序，而是在每一步贪心地选择当前能跳到的最远位置，不断更新可覆盖区间的右边界，直到到达终点。核心思想和这道分糖果题完全不一样，但底层的直觉是一致的：每一步都做局部最优选择，并证明这种局部最优不会破坏全局最优。

备赛时建议大家按“贪心训练清单”来刷题：先练排序型贪心，再练区间型贪心，再练区间调度、哈夫曼编码等进阶贪心。每道题做完后都要问自己两个问题：这个贪心为什么正确？交换论证还是反证法？写得出证明，这道题才算真正掌握了。

6.4 给备赛同学的三条具体建议

结合我带学生的经验，最后整理三条建议，直接照着做就行。

第一条，把贪心证明变成习惯。每次做完一道贪心题，花五分钟写出“为什么局部最优就是全局最优”。写不出来的话，说明还没吃透，回去重做。能写出证明的题，过一个月依然会做；只背结论的题，过一周就忘得干干净净。

第二条，用对拍积累边界敏感度。自己写题时，多写一个暴力函数去对拍，能快速发现排序漏了、边界错误、类型溢出这些问题。对拍脚本可以提前准备好，比赛前如果允许，带一个模板能省不少时间。

第三条，把第一题当成“保分题”来训练。平时练习时直接给自己 20 分钟限时，做完立刻对拍，错了分析原因。坚持一个月，你就能明显感觉到第一题不再慌，后面的题也有更多时间思考。

我个人带备赛时最喜欢用这类“排序 + 扫描”的题让学生做限时训练，因为它足够基础，能暴露很多问题，同时又能延伸到非常多的变体。这道“贪心的小朋友”建议你不管用什么语言，都亲手写一遍、证明一遍、变形一遍。三道工序走完，这一题你就真正吃透了。