我第一次在洛谷交这题用的是float。评测结果 WA 了两个点我盯着屏幕看了十来分钟也没想明白——循环次数明明对样例全过怎么一提交就挂后来学长瞥了一眼淡淡说了一句“换成 double”。改完 AC。从那以后我才意识到P1035 这种 NOIP 2002 普及组第一档的题表面上考的是循环实际上考的是精度、边界和你对数据范围的敏感度。P1035 级数求和大概是很多人在洛谷刷题清单里最早遇到的“数学味道”题目之一。题目不长输入一个正整数 k求最小的 n使得调和级数的前 n 项和 S 1 1/2 1/3 … 1/n 严格大于 k。适合刚学完循环结构的新手练手也适合准备普及组复赛的选手回头做一次“精度教育”。这题不会为难你的算法但会非常诚实地告诉你浮点数用错了类型代码写得再漂亮也白搭。1. 题目到底在考什么精度、边界和“为什么 k 只到 15”1.1 级数本身没有“捷径”只能一项一项加先把这个级数说清楚。S 1 1/2 1/3 … 1/n数学上叫调和级数。它有个著名性质虽然每一项都在变小但级数是发散的——也就是说只要 n 足够大S 可以超过任意给定的正数。问题是它发散得非常慢慢到什么程度大约 ln(n) γ其中 γ ≈ 0.5772 是欧拉常数。这不是废话它直接决定了这题该怎么做既然没有通项公式能一步算出“第几项超过 k”那就老老实实循环累加。这种“暴力”不是笨办法而是因为调和级数本身就没有优雅的封闭形式解。你在考场上一时半会儿推导不出 n 和 k 的显式关系题目也根本不需要你推导——它要的就是你“会循环”。1.2 k ≤ 15 是出题人给你的最重要暗示很多人刷题时只看输入输出格式不看数据范围。这是大忌。P1035 的 k 上限是 15这不是随便写的它直接说明了两件事第一累加项数在可控范围内。用欧拉常数估算一下想让 S 超过 15大约需要 n e^(15 - 0.5772) ≈ e^14.42 ≈ 183.5 万。183 万次循环对任何现代评测机来说都是毛毛雨C 几十毫秒跑完Python 也就一两秒。所以出题人敢把 k 放到 15就是因为暴力循环的时间复杂度完全挺得住。第二如果 k 上限是 100 或者 1000这题的性质就彻底变了。e^100 是个天文数字暴力循环会 TLE 到天荒地老。到时候题目就变成“用数学方法估算”“二分查找”甚至“打表预处理”。所以看到 k ≤ 15你其实应该立刻意识到本题就是让你循环的别想复杂了。1.3 “严格大于”三个字是边界陷阱的重灾区题面说的是求最小的 n使得 Sn k。注意是“大于”不是“大于等于”。也就是说如果 Sn 刚好等于 k那这 n 还不够必须继续往后加。举个最典型的例子k 1 时S1 1恰好等于 1。因为要求严格大于所以 n 1 不合格得继续加。S2 1.5S3 ≈ 1.833都大于 1所以最小的 n 是 3。如果你在判断条件里写了while (s k)或者s k时退出k 1 这组数据就会输出 2直接 WA。这个点几乎每年都会有人踩。2. 三种语言的完整实现与细节对照2.1 C 写法while 和 for 各有各的坑先给最经典的 while 写法#include iostream using namespace std; int main() { int k; cin k; double s 0; int n 0; while (s k) { n; s 1.0 / n; } cout n endl; return 0; }循环条件写成s k的意思是只要还没严格超过 k就继续加。这里一定要用s 1.0 / n而不能写s 1 / n。原因很简单在 C 里1和n都是 int1 / n是整数除法除了 n1 时等于 1其他时候全等于 0。如果你写1 / n那 s 永远只会在第一项加 1后面的项全部白加输出永远是 1。这个错误极其隐蔽因为样例 k1 时输出正好是 3能过样例但 k2 就彻底露馅。也有很多人喜欢用 for 循环#include iostream using namespace std; int main() { int k; cin k; double s 0; for (int i 1; ; i) { s 1.0 / i; if (s k) { cout i endl; break; } } return 0; }这种写法的逻辑是先累加再判断所以循环变量 i 本身就是答案不需要再加 1。它的判断条件和 while 版是对应的区别只在于习惯。我个人的建议是新手先用 while 版因为while (s k)更直观地体现了“没超过就一直加”这个语义不容易在边界问题上绕晕。可以用两组数据测一下自己的实现k 1正确答案 3k 2正确答案 41 1/2 1/3 1/4 ≈ 2.0833第 4 项才超过 2。如果这两组都对说明你的边界至少没写反。2.2 Python 写法注意版本差异和浮点精度洛谷也支持 Python而且写起来非常短k int(input()) s 0.0 n 0 while s k: n 1 s 1 / n print(n)Python 3 里1 / n默认就是浮点除法所以不像 C 那样容易踩整型除法的坑。但有一个历史遗留问题需要知道Python 2 里1 / n是整除会得到 0。虽然现在洛谷默认是 Python 3但如果你在别的 OJ 或者自己电脑上还在用 Python 2 环境这个坑会再现。另外Python 的 float 底层就是 C 的 double精度跟 C 的 double 一致本题放心用。实测下来Python 跑 k15 的那组数据大概在一秒多不会 TLE。如果你担心 Python 循环慢也可以把s 1 / n改成s 1.0 / n全用浮点字面量少一次隐式转换。性能提升微乎其微纯粹图个心理安慰。2.3 Java 写法提交时类名必须是 Main用 Java 刷洛谷最容易翻车的地方反而不是算法而是类名。洛谷要求提交的 Java 代码必须用Main作为公共类名import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int k sc.nextInt(); double s 0; int n 0; while (s k) { n; s 1.0 / n; } System.out.println(n); sc.close(); } }Java 里的1.0 / n同样是浮点除法没问题。n用 int 就够了因为答案最多也就 183 万左右远小于 int 上限 21 亿。这里反而要提醒不要画蛇添足把 n 定义成 long虽然不影响正确性但会让人觉得你没估算过数据范围。三种语言的核心差异我用个表总结一下方便对照对比项CPython 3Java浮点类型doublefloat底层 doubledouble整型除法陷阱有必须写 1.0/n无Python 3有必须写 1.0/n典型循环用时k15几十毫秒一秒左右几十毫秒最容易犯的错1/n 整除无类名不叫 Main3. 那些让洛谷给你“80分”的坑一份排错实录洛谷上经常有人发帖问“我这题为什么只拿 80 分”例如热门问题里就有类似“P10472 为什么只拿 80 分”的疑问。80 分在洛谷是个很典型的分数含义通常是大部分测试点都过了但有一两个点 WA 或者 TLE。P1035 虽然是最简单的入门题但如果你拿到 80 分而不是 100 分基本跑不出下面这几个原因。3.1 float 精度不足最隐蔽的扣分点这是我在开头提到的问题。float大约只有 7 位有效十进制数字而double有 15 到 16 位。这题要累加 183 万项每一项都是分数的小数形式累加过程中误差会不断累积。尤其当 s 接近 k 时最后一步的精度直接决定了你输出的 n 是偏大还是偏小。很多人以为 float 够用是因为样例和大多数测试点的 k 都很小。k 小的时候累加次数少误差不明显。但 k 15 时近两百万次累加之后误差足以让最后一项判定出错。这就是为什么你会“样例全过、提交挂点”。结论很明确涉及浮点数累加的题目默认用 double不要用 float。这不是小题大做而是经验之谈。3.2 整型除法和“等于”边界两个经典的 WA 来源整型除法前面已经说过1 / n在 C/Java 里是整除。这里不再重复但我要强调它的隐蔽性。因为你大概率能过 k1 的样例然后自信满满地提交接着被一个测试点教做人。边界问题也值得单独列出来。判断条件里的“严格大于”写成和结果完全不同。我在第一节说过 k1 的例子这里再补充一个自查方法提交之前先手动跑边界测试。具体来说把 k 分别设为 0、1、15 跑一遍本地确认输出分别是 1、3、1835421。这三个值覆盖了最小值、相等边界和最大值任何一个不对都说明你的判断条件有问题。3.3 输出格式多打空格也算错洛谷对输出格式的要求很严格但很多新手不知道。比如有些人会在输出语句里写cout n 或者printf(%d , n)觉得多一个空格无所谓。其实这是错的。评测机是逐字符比对输出文件多余的空格、换行都有可能被判 WA。P1035 的输出只有一行就是一个整数 n不多不少。3.4 死循环和 TLE 的几种可能还有一种 80 分不是 WA 而是 TLE虽然这题很少见但确实有人会犯。最常见的写法错误是在 while 循环里忘了给 n 递增或者把条件方向写反。比如while (s k) { s 1.0 / n; // n 永远不增加 }这种代码会在 k 较小时碰巧输出一个值但 k 大一点就直接死循环。排查方法很简单本地跑一下 k15如果程序几秒钟出不来结果那代码十有八九有死循环。还有一种情况是用while (s k)且初始 s0这在逻辑上等价于s k-1某些 k 值下会少加一项输出结果偏小 1也是 80 分常见的“差一项”问题。提示这类入门题讲究的其实不是算法复杂度而是一丝不苟。你可以建立一个自己的“提交前检查清单”数据类型对不对、边界条件测没测、输出格式规不规范。这三项全过基本就稳了。4. 从级数求和延伸出去这题背后藏着的刷题方法论4.1 前缀和思维动态规划题单的前菜P1035 的累加过程本质上是在维护一个“前缀和”。你在循环里不断把新的1.0 / n加到 s 上s 始终表示“前 i 项的总和”。这个思维模式在后面的刷题路上会反复出现。比如洛谷动态规划题单里的很多题第一步都是预处理前缀和再基于前缀和做状态转移。再比如区间求和类问题sum[i] sum[i-1] a[i]这种递推式子如果你在 P1035 里就已经建立了“累加器”的直觉后面理解起来会顺畅得多。所以别小看这道题它是很多算法思想的雏形。4.2 单调性与“第一个满足条件的位置”调和级数是严格单调递增的所以“第一个满足 Sn k 的 n”本质上是一个单调序列上的查找问题。由于单调你可以线性扫描如果 n 的范围再大一点你还可以二分。P1035 因为 k ≤ 15线性扫描完全够用但这道题背后隐藏了一个重要的算法原型在一个有单调性的序列上找到第一个满足条件的位置。这个原型在普及组提高组的题目里很常见。比如某些二分答案题第一步要证明答案具有单调性然后才能二分。你可以在学完二分之后回到 P1035 试着用二分重写一遍对 n 进行二分检查S(n) k是否成立。这会是一道很好的二分练习题。不过现阶段不用过度设计循环能过就别给自己加戏。4.3 自己造数据从“靠样例”进化到“主动验证”很多人刷 OJ 题有个坏毛病写完代码拿样例一测过了就提交挂了就一脸懵。正确做法是主动给自己造测试数据。P1035 这种题的数据范围很小你完全可以在本地验证所有边界k 0此时 S1 1 0所以输出 1k 1S1 1 不满足严格大于继续加到 S3 ≈ 1.833输出 3k 15输出 1835421。如果你已经学会写简单的对拍脚本还可以写一个小程序随机生成若干 k再用 Python 的高精度fractions模块算正确的 n对比你的 C 程序输出。这是做 OJ 题的一项核心能力构造数据、验证正确性、缩小 bug 范围。别嫌麻烦这套流程以后解难题时价值巨大。4.4 把它玩成“小游戏”跑答案、看增长、找直觉说实话我见过有同学把这道入门题玩成小游戏每跑出一个 k 对应的 n就记下来观察 n 的增速再跟公式e^(k-γ)对比看误差多大。这种玩法听起来幼稚但对培养数学直觉特别有用。你会直观感受到“指数增长”和“调和级数慢发散”到底是什么概念比光看课本上的定义印象深刻得多。另外如果你刷腻了中文题面洛谷国际站上也有同样的题单和题目换英文题面读一遍顺带练练读题能力。百利而无一害。5. 最后分享一点个人体会我现在看 P1035已经不用想就知道答案大概在什么量级但每次给新手讲这道题还是会反复强调三件事double、严格大于、边界测试。因为这三个点不止出现在这一题它们几乎是所有入门类题目的通用教训。我个人有个习惯写完任何一道题哪怕再简单也会把它的边界数据测一遍。k0、k1、k15 这三组数据基本就是 P1035 的全部边界。很多时候你觉得自己“会了”其实只是样例“提示”了你真正测试是自己造出来的这一点越早明白越好。刷题这件事P1035 只是个起点。后面你会遇到更复杂的二分、动态规划、图论但基础打得牢不牢往往就体现在这些微不足道的细节里。