级数求和这四个字当年在 NOIP 2002 普及组的考场上劝退过不少人。我到现在还记得旁边一个同学翻到第一题看到级数两个字直接翻到最后去看第四题回来又盯着题面看了半天最后空着交了卷。其实这道题剥掉所有吓人的名词就是一个 while 循环的事。P1035 是洛谷上这道题的编号题面很短输入一个正整数 k找到一个最小的正整数 n使得 1 1/2 1/3 …… 1/n 的和大于 k输出这个 n。k 的范围是 1 到 15。注意它不是求数学上的闭式解也不是让你证明级数收敛性它考察的是最朴素的枚举能力——你敢不敢在一个看起来像数学题的外壳下直接一遍遍地加。这篇文章不只是给 AC 代码。我会把为什么暴力能过、循环边界怎么注意、浮点精度坑在哪、提交前要检查哪些细节以及这道题背后连着的调和级数和二分思想都拆开讲一遍。适合刚入门信息学竞赛的选手也适合带学生的老师拿来讲第一节课的破胆题。1. 题面拆解别被级数两个字吓住1.1 题目真正只问了两件事原题描述本质上就一行话给定 k1 ≤ k ≤ 15求最小的 n使得 1 1/2 1/3 ... 1/n k。输入一个整数 k输出一个整数 n没有别的了。手动跑几组k1 时1/1 1不大于 1再加上 1/2得到 1.5大于 1所以答案是 2。k2 时前三项是 1.833...还不够加上第 4 项后是 2.083...大于 2所以答案是 4。k3 时前 10 项约 2.929不够前 11 项约 3.0199够所以答案是 11。这个逻辑用代码写出来就是维护一个和 sn 从 1 开始每次加 1把 1/n 累加进去直到 s 严格大于 k。题目只要 n不要输出那个和所以程序里只需要一个 double 变量存和一个 int 变量记位置空间复杂度 O(1)。很多刚学的同学一上来就把问题复杂化了又是数组又是结构体完全没必要。1.2 为什么这题放在普及组第一题第一题的位置是有讲究的。它不考验高级算法而是考验选手看到一个陌生名词能不能把它翻译成自己会的东西。级数这个词在高中数学里往往到选修才正式出现而在高等数学里又有专门的级数理论。竞赛题用它当标题对很多初一、初二刚接触信息学的选手来说第一眼的压力不小。但实际上你只需要发现一件事这个和是随着 n 增大单调递增的。既然单调递增又有数据范围约束直接从 1 往上累加就可以。这就是信息学竞赛里最核心的思维之一分析数据范围选择最朴素的解法。NOIP 2002 年的时候评测机比现在慢得多但 k≤15 这个约束决定了暴力的循环量级只有百万级当年跑完毫无压力今天更不用说。很多选手在这道题上真正的难点不是算法而是敢不敢动手写循环。2. 暴力循环为什么是正解先把复杂度这笔账算明白2.1 调和级数涨得有多慢1 1/2 1/3 1/4 ... 这个数列有一个专门的名字叫调和级数。它的特点是项越来越小和增长也越来越慢慢到超出不少人的直觉。看几个值就明白了nH_n1110约 2.93100约 5.191000约 7.491000000约 14.39加到 100 万项和竟然还不到 15。这就是题目敢把 k 的最大值设成 15 的原因——如果 k 设成 100暴力循环量级会到 e^99 这种天文数字题目完全变性质。那 k15 时到底要加到多少用近似公式先估一下H_n ≈ ln(n) γ其中 γ ≈ 0.57721。要 ln(n) 0.577 15就得 n e^14.42约等于 1.83×10^6。我多次验证过精确的最小 n 是 1,835,421。也就是说最坏情况下循环不到 184 万次。2.2 每秒钟能跑多少循环184 万这个数字很多人对它的执行时间没有直观概念。现代 OI 评测机上单纯做整数加法循环每秒跑到 1e8 次也不稀奇这里每次循环做一次浮点除法、一次浮点加法、一次浮点比较速度会慢一些但保守估计也能到每秒两三千万次。184 万次循环意味着运行时间只有几十毫秒哪怕评测机再差1 秒时限也绰绰有余。所以这道题的答案就是暴力。不需要想什么高级公式也不需要先求个近似值再修正。很多人做题有个习惯性误区看到数学题就觉得自己得用数学方法秒杀反而把一个简单循环题折腾成一堆浮点误差的麻烦。2.3 为什么不能靠公式直接反解出答案那有人会问既然 H_n ≈ ln(n) γ直接解对数不就行了这里有一个隐蔽的坑近似公式是约等不是等。在临界值附近近似误差完全可能跨越好几个整数。比如用它算 n ≈ 1,835,421但真实边界可能是 1,835,420、1,835,421、1,835,422 中的任意一个靠近似公式无法确定精确值。要证明一个整数 n 就是精确的答案你需要严格证明 H_{n-1} ≤ k 且 H_n k。用近似公式做这个证明误差界很难处理远不如直接循环来得干净。因此竞赛里有一个通用原则数据范围允许时暴力永远是最优先的方案。公式和近似的作用是帮你估量级、定二分边界而不是用来取代直接计算。3. 从WA到AC浮点精度与循环边界这两道坎3.1 新手最容易写出的WA版本先看一个典型的错误写法#include iostream using namespace std; int main() { int k; cin k; int n 1; double s 0.0; while (s k) { s 1 / n; // 问题出在这一行 n; } cout n endl; return 0; }这段代码的致命问题在1 / n这一行。在 C/C 里1和n都是 int两个 int 相除结果是整数除法会把小数部分直接截断。n2 时1 / 2的结果是 0不是 0.5。于是从第二项开始s 永远加的是 0整个程序会无限循环下去直到超时。这是一个非常经典的 C 入门坑几乎每个新人都踩过。解决办法是让其中一个操作数变成浮点数s 1.0 / n;写成1.0 / n或1.0 * 1 / n都可以核心是浮点数和整数做除法时整数会被自动转成浮点数结果是浮点除法。3.2 改对之后的AC版正确的写法可以这样#include iostream using namespace std; int main() { int k; cin k; int n 0; double s 0.0; while (s k) { n; s 1.0 / n; } cout n endl; return 0; }逻辑说明n 从 0 开始每轮先把 n 加 1再往 s 里累加第 n 项。这样退出循环时n 恰好就是当前加到的项数不用再调整。Python 版本也很直观k int(input()) n 0 s 0.0 while s k: n 1 s 1 / n print(n)Python 3 里1 / n默认就是浮点除法少踩一个整数除法的坑。但如果用的是 Python 21 / n又变回整数除法这也是很多老代码翻车的原因。如果混用不同语言版本一定要确认自己的除法语义。3.3 float、double和long double一次WA换来的教训那用 float 类型行不行我的建议很直接不行。float 只有大约 7 位十进制有效数字。当和累加到 15 附近时float 能分辨的最小变化只有 1e-6 左右。而第 1,835,421 项的值是 1/1835421约等于 5.45e-7这个量级已经小于 float 在当前数值下的精度分辨率。更要命的是浮点累加本身有舍入误差。每一次s 1.0 / n都会把结果舍入到 float 能表示的最近值累加 180 多万次误差可能积累到 1e-4 甚至更大。在边界附近这个误差完全可能让判断多算一次或者少算一次。double 有大约 15 到 16 位有效数字在这种循环量级下累加误差远小于判断所需的精度不会影响最终整数答案。long double 更稳但对这道题没有必要。我实际遇到过有人用 float 提交恰好 k15 的边界判错了输出 1,835,422 而不是 1,835,421直接 WA。改成 double 之后立刻 AC。从那以后凡是涉及浮点和累加的竞赛题我默认用 double只有在内存极紧张或者明确知道精度足够时才考虑 float。4. 提交前的自查清单边界数据、类型选择与输出格式4.1 先手算几组边界数据提交前建议先拿小数据手算一下确认程序行为和预期一致。k最小 n验证过程121 1/2 1.524前三项 1.833第四项后 2.083311前10项 2.929前11项 3.0199431前30项约 3.995前31项约 4.027151835421前面已经估算过用 k1 验证程序能正常退出用 k15 跑一遍观察循环次数大概是 183 万。如果 k15 跑了上亿次甚至卡死十有八九又是整数除法或者循环条件写反了。还有一个常犯的错有人喜欢把初始值写成s1、n1然后从 2 开始加。这本身没有问题但循环边界和初始值必须配套调整很多人改着改着就乱了。我的建议是统一使用n 从 0 开始每轮先 n再加 1.0/n这个模板逻辑最干净也最不容易出错。4.2 输出格式别大意P1035 只要求输出一个整数 n不要求保留几位小数更不用输出和。我见过不少无谓的失误用printf(%.2f, n)输出n 是 int格式符和类型不匹配轻则告警重则 CE 或乱码。输出多一个空格或多一个换行遇到严格评测会判 PEPresentation Error。竞赛纪律就是多输出一个空格都算错。使用cout时忘记endl或者\n导致输出堆积。本题只输出一个整数问题不大但养成每个输出都带换行的习惯会更稳妥。4.3 评测机制和文件IO的坑洛谷这类 OJ 上P1035 用的是标准输入输出不需要 freopen。直接cin k就行。但如果你在本地模拟 NOIP 环境或者参加正式比赛题目可能要求文件 IO。这时候要注意题目说明里的输入文件名和输出文件名比如有些题要求sum.in和sum.out并需要在代码开头写freopen(sum.in, r, stdin); freopen(sum.out, w, stdout);再强调一遍P1035 在洛谷上不需要这个加了反而可能导致本地没有对应文件而读不到输入。判断依据永远是题目的输入输出说明不要拍脑袋。另外如果题目没说明多组测试就老老实实按单组处理。有些人习惯性写个while (cin k)想让程序同时支持多组数据但评测只给一个 k多出来的输出不会被比对反而可能导致格式错误。5. 题外功调和级数、欧拉常数和二分思想的起点5.1 调和级数为什么发散P1035 只是无数调和级数变体题里的一粒沙。如果只看这题的 k 范围你可能觉得和增长慢而已但调和级数有一个更深的性质它发散了也就是说无论你给定多大的数都存在某个 n使得前 n 项和大于它。直观的证明是分组法。把项按 2 的幂分组第 1 项1第 2 项1/2第 3 到 4 项每项都 ≥ 1/4合计 ≥ 1/2第 5 到 8 项每项都 ≥ 1/8合计 ≥ 1/2第 9 到 16 项每项都 ≥ 1/16合计 ≥ 1/2每组至少贡献 1/2而这样的组可以无限分下去所以和可以超过任意大的数。这和 k≤15 一对比就更能理解为什么 n 要到 183 万了。如果把 k 改成 100n 会大到约 1.5e43 这个量级不仅是循环没法跑连直接数都数不过来。5.2 用欧拉常数做估算调和级数和自然对数之间有一个著名的近似关系H_n ≈ ln(n) γ这里的 γ 是欧拉常数约等于 0.5772156649。这个公式在信息学竞赛里最常用的地方有三个一是估算上界。比如写二分答案时需要确定 r 的最大值可以用它算一个足够大的数#include iostream #include cmath using namespace std; int main() { int k; cin k; int r (int)exp(k - 0.57721) 100; cout r endl; return 0; }这个 r 只是一个估算作为二分的上界够用但不要直接把它当答案输出原因前面说过近似公式不能精确确定边界。二是对拍验证。赛后怀疑自己的暴力循环是不是跑多了可以用这个公式算出的理论值和实际循环数对比两者差在个位数内就说明程序没有大方向错误。三是在题目 k 的取值范围很大的情况下快速判断暴力是否可行。5.3 如果k变大单调性、二分答案和离线处理如果题目改成 T 次询问每次给一个 k求最小 n那暴力每次从头累加 O(n) 就会很吃亏。但这个问题有一个很好的性质H_n 随着 n 单调递增。单调性意味着可以二分答案——只要你能快速求出任意位置的 H_mid。二分答案的模板长这样int l 1, r 2000000; // r 根据 k 上限调整 while (l r) { int mid (l r) / 2; double s 0.0; for (int i 1; i mid; i) s 1.0 / i; if (s k) r mid; else l mid 1; } cout l endl;注意这里每次判断 mid 都要现场循环计算总复杂度是 O(n log n)大约两千万次浮点运算1 秒内勉强也能过但显然不如直接暴力。真正的优势在于多组询问场景可以预处理前缀和数组或者对询问离线排序后统一扫描。这种单调性 二分答案的模型在这道入门题里第一次出现后面很多题目都会反复用到。比如网格图上的最短路径消耗满足单调性就能对答案进行二分比如某些最优值问题通过二分把求最优转成判断可行可行性判断比最优求解简单得多。P1035 给的是一个最朴素的例子答案只有一个整数判断方式是简单的累加。顺带一提[NOIP 2017 普及组] 的棋盘那道题用的是另一种思维模型搜索加状态转移。不同题目训练的是不同的模块而 P1035 负责训练的就是把数学名词翻译成循环和数据范围驱动解法选择这两件事。把这种直觉练成肌肉记忆之后以后看到再唬人的题面第一反应也会是先分析数据范围而不是先被名词吓住。