简介这是一份为算法竞赛初学者准备的在线评测题库经典题解完整收录了北大在线判题系统上题号为一千零三、英文名为Hangover的经典问题的解题报告和已获通过的C源代码。题目要求通过不断叠加长度按比例递减的卡片计算出至少需要多少张卡片才能超过给定的目标长度核心考察浮点数累加、循环终止条件以及边界情况的处理。压缩包内共有两个文件一份文档用于呈现问题分析、推导过程和复杂度说明另一份为C语言实现的可运行源码全部压缩后大小仅为八KB。目前已有三百一十七人学习下载。对于刚开始接触算法竞赛、希望熟悉在线评测提交流程的读者这份资料既能提供清晰完整的解题思路又能通过实际代码展示如何将思路落地为程序可作为日常刷题与撰写解题报告时的参考范本。 POJ 1003Hangover这大概是很多人在北大OJ上刷的第一道题。我第一次打开题面时看到“宿醉”这个标题又看到一堆卡片从桌沿伸出来一时没搞懂这跟酒精有什么关系。多读几遍才意识到题目只是用一个物理场景包装了一个很朴素的数学问题输入一个浮点数 c程序要找最小的卡片数 n使得 1/2 1/3 … 1/(n1) 至少达到 c。输入以 0.00 结束输出格式固定为 “N card(s)”。这题的算法难度几乎为零但它非常适合训练一个 OJ 新手最需要的三件事读懂题目公式、处理好浮点比较、严格遵守输出格式。下面就从这三个角度把这题彻底拆开讲一遍。1. 先读懂题面在问什么从卡片悬伸到调和级数1.1 题面故事与输入输出约定题面讲了一个很经典的物理场景每张卡片长度为 1把它们一张叠一张放在桌子边缘整体能悬伸出桌沿多远。题目直接给出了结论1 张卡片能伸出 1/22 张卡片能伸出 1/2 1/33 张卡片能伸出 1/2 1/3 1/4依此类推。也就是说第 i 张卡片带来的增量是 1/(i1)不是 1/i这一点很容易看错。输入是多行浮点数每行一个 c范围是 (0.00, 5.20]最后用一行 0.00 表示结束。对每个 c输出最少需要的卡片数格式固定为 “N card(s)”N 是整数括号是英文半角括号。这里要注意不管 N 是 1 还是 100都统一写成 card(s)没有单复数变化。这样一个简单的规则当年确实劝退了不少第一次使用 OJ 的人多一个空格、少一个括号结果都是 WA。1.2 公式含义从哪来要不要证明如果你看过经典的“一叠砖”问题会觉得这个公式很眼熟。一叠砖块从桌沿伸出每块相对下一块伸出一定比例整体刚好不倒最大悬伸长度会和调和级数有关。POJ 1003 的数据模型本质上就是这个经典问题的简化版本但题目并没有让你现场推导力矩平衡而是直接把悬伸长度公式给定了。做题的时候真正重要的是把它抽象成数学求和用 n 张卡片时总悬伸长度为sum(n) 1/2 1/3 ... 1/(n1)如果引入调和数 H_m 1 1/2 ... 1/m那么 sum(n) H_{n1} - 1。每个测试输入的目标 c就是要找最小的 n使得 sum(n) ≥ c。注意求和下标从分母 2 开始而不是从 1 开始所以答案不是在找 H_n 本身而是找 H_{n1} - 1。我最早写代码时把分母从 1 开始累加结果答案是错的检查了半天才发现差了一项。1.3 用欧拉常数估算答案规模既然 c 最大才 5.20看起来似乎要循环很多次但调和级数增长非常慢。调和级数有个近似公式H_m ≈ ln(m) γ 1/(2m)其中 γ 是欧拉常数约等于 0.5772156649。代入这道题的场景要满足 H_{n1} - 1 ≥ 5.20也就是 H_{n1} ≥ 6.20。估算一下ln(n1) 0.5772 ≈ 6.20ln(n1) ≈ 5.6228n1 ≈ 277也就是说即使输入是最大的 5.20需要的卡片数也只有 276 张左右。这个结论很关键它直接决定了我们选用什么算法都不会超时暴力循环几百次完全没问题。我在初学阶段经常被“5.20”这种数字吓到以为要处理很大的数据量实际上通过数学估算之后心里就有底了。2. 两种实现路线暴力累加与预计算二分2.1 暴力累加最直接也最不容易错暴力思路和题面描述完全一致用一个变量 len 记录当前累计长度从分母 2 开始每次加 1.0/den同时计数 cnt 加一直到 len 大于等于 c输出 cnt。因为答案最多只有几百单次查询的时间复杂度是 O(ans)即使有几十组输入也只是几万次浮点加法在 POJ 上跑起来是瞬间完成。对刚入门的人来说我建议先把这种最朴素的写法做出来并提交通过再去想进阶写法。它能帮你确认自己对题面公式的理解是否正确。写的时候有几个小坑分母要用 double 计算不要写成 1/den 这种整数除法循环条件建议写成len 1e-9 c而不是len c这样能避开浮点误差边界问题。后面我会专门解释为什么。2.2 预计算前缀和加二分一次算完多次查询如果输入有很多行每次都从零开始累加虽然不至于超时但确实是重复劳动。更漂亮的思路是预计算一张前缀和表定义sum[i]表示 i 张卡片的最大悬伸长度也就是sum[0] 0sum[1] 1/2sum[2] 1/2 1/3sum[i] 1/2 1/3 ... 1/(i1)因为 c 最大不超过 5.20我们只需要从 i1 开始一直累加到某个值超过 5.20 为止。这个表是严格单调递增的。之后每次查询只要在这个递增数组里找到第一个 ≥ c 的位置这个位置的下标就是答案。单次查询从 O(ans) 降到了 O(log n)因为用的是二分查找。这个“预处理 查询”的套路在以后很多题目里都会反复出现比如前缀和数组、segTree 的预处理、离散化后的二分查找。通过这道题把 lower_bound 的语义吃透是很划算的。2.3 两条路线的取舍建议说实话POJ 1003 用暴力写完全能过预计算二分属于锦上添花。但为什么我还是建议你两种都写一遍因为二分版本能帮你理解一个非常核心的 STL 函数lower_bound返回的是第一个不小于目标值的迭代器位置。这个语义在本题里恰好对应“最少需要的卡片数”。如果序列里正好存在等于目标值的元素它返回的是这个元素的位置如果不存在它返回的是第一个大于目标值的位置。另外预计算版本还有一个隐藏价值sum数组可以直接复用。如果题目改成“给定卡片数 n求最大悬伸长度”你只需要查表sum[n]就能 O(1) 回答。这种“一张表服务多个问题”的思维对后续刷题帮助很大。所以我个人的建议是暴力写出并 AC 之后再花十分钟把二分版写了两版对比着提交一次对这道题的理解会上升一个层次。3. 三个容易翻车的细节浮点比较、终止条件、输出格式3.1 浮点比较为什么建议加一个极小量double 在存储 1/2、1/3 这类分数时用的是二进制近似实际数值和十进制理论值之间有极小的误差。比如理论上累加结果是 1.0实际存储可能是 0.9999999999999999也可能是 1.0000000000000002。如果你写死while (len c)在 len 理论上应该等于 c 的边界位置可能因为误差被判成 len 比 c 小于是多循环了一次答案就比预期大 1。处理方式是在比较时加一个极小量 epsilon通常用 1e-9 就够。循环条件写成while (len 1e-9 c) { // 继续累加 }这样 len 理论上等于 c 时len 1e-9 c循环正常退出。同理在二分版本中最稳妥的做法是用lower_bound去找c 1e-9或者把预计算上界多留一点比如累加到5.20 1e-6再停止。这样即使最后一个元素因为浮点误差差了一点点也不会出现查不到结果的情况。3.2 输入终止条件用 c 0 而不是 c ! 0多组输入以 0.00 结束很多人的第一反应是写while (scanf(%lf, c) 1 c ! 0.0)。这个写法本身能过但我更推荐写成c 0。原因很简单0.00 转成 double 就是 0.0用c ! 0.0不会出错但如果你读了题发现输入约定是正浮点数加一个终止标志用c 0表达的语义是“所有正常数据都继续处理遇到 0 或异常值直接结束”更安全。Java 里我习惯写成if (c 0) break;这样把 0.0 和潜在的负值一起排除掉。还有一个常见的低级错误有人会把 c 当做整数读写成scanf(%d, c)结果 1.00 被截断成 1精度全丢。这个在初学 C 语言时非常容易犯记住输入浮点数必须用%lf。3.3 输出格式card(s) 就是 card(s)POJ 的输出比对是逐字符精确匹配的所以格式问题一定要较真。这个题要求每行输出 “N card(s)”N 和 card 之间一个空格括号是英文半角括号。我第一次提交时觉得“一张卡片”应该是 “1 card”于是写了单复数判断结果直接 WA。其实题面要求很死板不管几张卡片永远是 card(s)没有单复数之分照着原样输出即可。还有一个隐藏陷阱如果你用printf建议写printf(%d card(s)\n, cnt);注意不要在括号前后加多余空格也不要用中文括号。Java 里用System.out.printf(%d card(s)%n, cnt);也是同理。OJ 刷多了你就会发现很多简单题的 WA 不是因为算法而是因为输出格式差了一个空格或者少了换行。4. 可直接提交的完整代码C 与 Java 双版本4.1 C 暴力版本#include cstdio int main() { double c; while (scanf(%lf, c) 1 c 0) { int cnt 0; double len 0.0; int den 2; while (len 1e-9 c) { len 1.0 / den; den; cnt; } printf(%d card(s)\n, cnt); } return 0; }这段代码的核心在循环里den 从 2 开始每累加一次1.0/denden 加 1cnt 加 1。cnt 最终就是卡片数。注意我用了1.0 / den而不是1 / den因为整数除法结果永远是 0。用len 1e-9 c做循环条件是为了避开浮点误差这个习惯建议直接记下来。4.2 C 预计算加二分版本#include cstdio #include vector #include algorithm std::vectordouble sum; int main() { sum.push_back(0.0); double s 0.0; int i 1; while (s 5.20 1e-6) { s 1.0 / (i 1); sum.push_back(s); i; } double c; while (scanf(%lf, c) 1 c 0) { int ans std::lower_bound(sum.begin() 1, sum.end(), c 1e-9) - sum.begin(); printf(%d card(s)\n, ans); } return 0; }这里sum[i]的含义就是 i 张卡片的最大悬伸长度所以lower_bound返回的迭代器位置减去begin()正好是答案。预计算循环条件写成s 5.20 1e-6是为了保证最后一个元素一定大于等于 5.20避免在边界处查不到。查找时传入c 1e-9相当于把目标值稍微放大一点补偿浮点存储误差这个技巧在后续很多浮点二分的题目里同样适用。4.3 Java 版本与 POJ 提交注意事项import java.util.*; public class Main { public static void main(String[] args) { ArrayListDouble sum new ArrayList(); sum.add(0.0); double s 0.0; int i 1; while (s 5.20 1e-6) { s 1.0 / (i 1); sum.add(s); i; } Scanner sc new Scanner(System.in); while (sc.hasNextDouble()) { double c sc.nextDouble(); if (c 0.0) break; int ans Collections.binarySearch(sum, c 1e-9); if (ans 0) ans -ans - 1; System.out.printf(%d card(s)%n, ans); } } }Java 的Collections.binarySearch和 C 的lower_bound有一点不同如果找到了精确值返回对应下标如果没找到返回负值表示为-(插入点) - 1。所以当返回值小于 0 时要取反减一得到插入点也就是第一个大于目标值的下标。这段代码里我传的是c 1e-9也是为浮点误差留出缓冲。POJ 提交 Java 有几个老坑类名必须是Main不能带 package而且 POJ 的 Java 版本比较老不要用 var、lambda 这些较新的语法。我第一次在 POJ 提交 Java 时用了 Java 11 的var写法结果编译错误改成传统写法才通过。如果你用的是老 JDK老老实实写Iterator或者for循环不要追求语法酷炫。5. 这道题的延伸逆问题、欧拉常数与刷题心态5.1 逆问题已知卡片数求最大悬伸长度POJ 1003 只考了“给定目标长度求最少卡片数”那反过来呢如果题目改成“已知 n 张卡片最大能悬伸多长”答案就是sum[n] 1/2 1/3 ... 1/(n1)。你只需要预计算一张前缀和表就能在 O(1) 时间内回答任意 n。这说明预计算数组不只是为了解决当前这组查询它把问题模型本身固化了。以后刷到区间和、前缀和最值这些题你会发现同样思维随处可见把重复计算变成一次性预处理把查询变成查表或二分。5.2 调和级数与欧拉常数这道题背后的数学对象是调和级数它在算法复杂度分析里经常出现比如快速排序的期望复杂度、哈希表探测的平均步数都会涉及 H_n。调和级数本身是发散的但 H_n - ln n 收敛到欧拉常数 γ ≈ 0.5772156649。这个性质可以用来估算很多累加题目的答案规模比如本题中 5.20 对应的卡片数只有 276 左右。我当时第一次算出来这个数字时还挺惊讶因为 5.2 看着比 1/2 大得多但调和级数增长实在太慢。理解了这一点以后再看到复杂度里带 log 的项你会更有直觉。5.3 对刷题起步阶段的两点个人建议第一第一次提交如果 WA 了不要急着怀疑算法先看输出格式再看边界条件最后再查逻辑。POJ 1003 就是这种“算法简单但格式严格”的典型非常适合用来建立这个排查顺序。第二不要满足于一种解法。暴力过了再写一遍预计算加二分把 C 和 Java 都提交一次体会语言之间的输入输出差异。这道题虽然简单但它完整覆盖了“读题—建模—预处理——回答查询”这条解题链路。把它吃透你后面刷很多基础题都会顺畅得多。本文还有配套的精品资源点击获取