简介面向POJ算法竞赛学习者的经典题目资料包内含POJ1003-Hangover的完整解题报告与C版AC代码。题目来自北京大学在线判题系统编号1003通常考察浮点数累加、二分查找或数学推导能力借助这份资料读者可以完整经历从读题、设计算法到提交通过的解题闭环。压缩包共2个文件、约8KBpoj1003-hangover.cpp为C源码适合直接运行对照研究边界条件与精度处理poj1003-hangover.doc为文字版解题报告从问题背景、输入输出格式、算法设计及时间/空间复杂度等角度展开帮助理解每一步推导。已有317人学习下载适合刚接触POJ、想通过典型题快速提升编程与算法能力的读者也可作为ACM/ICPC、蓝桥杯等竞赛的基础训练素材。阅读时先看解题报告理清浮点数累加、二分查找等核心思路再逐行分析AC代码能有效掌握一类精度计算与二分搜索问题的处理技巧为后续更复杂的算法学习打好基础。1. 题目概览一道经典入门题的底层逻辑第一次在POJ上看到“Hangover”这个题目时很多人的第一反应是这名字怎么这么奇怪挂机宿醉实际上这个单词在这里的意思是“悬挂、悬垂”——想象你正在桌面上叠一摞扑克牌每张牌向外伸出一点点最终这摞牌能悬空伸出桌面多远这个物理场景就是POJ 1003的题面原型。先说结论这是一道典型的“数学模拟 浮点数精度处理”的入门级题目适合刚接触在线评测系统OJ的算法新手也适合想复习浮点数边界问题、循环控制逻辑的选手。题目本身不涉及复杂数据结构也不需要高级算法思想但它足够经典几乎每一届ACM新生训练、每一本算法入门教材都会把它作为“热身题”收录。题面要求其实非常简洁给定一个浮点数 c范围在 0.01 到 5.20 之间要求找出最小的正整数 n使得下面这个累加和第一次达到或超过 c1/2 1/3 1/4 ... 1/(n1) c输出这个 n。输入以0.00结束每个测试用例输出一行比如对于1.00答案是3因为 1/2 1/3 0.8333 1.00加上 1/4 后约 1.0833刚好超过。听起来很简单确实简单。但就是这道“简单题”每年都有大量新手在细节上栽跟头WAWrong Answer到怀疑人生。这篇文章我就从题目本身的数学背景、代码实现细节、常见坑位和出题人的“小心思”几个角度把这道题彻底拆透。2. 思路拆解为什么这道题值得认真对待2.1 题目背后的数学本质调和级数这道题累加的序列 1/2 1/3 1/4 ... 其实是一个“缺了第一项”的调和级数。完整的调和级数是 1 1/2 1/3 1/4 ...而这里从 1/2 开始本质上就是调和级数减去 1。为什么要说这个数学背景因为调和级数有一个非常重要的性质虽然它每一项都在变小但它是发散的也就是说只要项数足够多累加和可以超过任意给定的正数。题目把输入上限设为 5.20其实是给了你一个“台阶”——在这个范围里你不需要考虑“累加和可能永远不够大”的问题直接暴力累加一定能在有限步内达到目标。5.20 这个上限是怎么来的我实际验证了一下当 n 约等于 227 时累加和才第一次超过 5.20。也就是说即便最坏情况你也只需要循环两百多次循环次数非常小。所以这道题的解法和“性能优化”基本沾不上边它考察的真正重点在于浮点数比较的精度问题循环边界的控制对“第一次达到或超过”这个条件的准确判断。如果你在这道题里用了什么“高精度算法”“数学公式直接求 n”那反而是把简单问题复杂化了。2.2 朴素模拟暴力累加就是最优解既然循环次数最多只有两百多次那最直接、最不容易出错的方案就是“模拟累加”——用一个变量sum从 0 开始每次加上1.0 / (i 1)i从 1 开始递增直到sum c时跳出循环输出当前的i。这个方案的优点是思路直白逻辑与题面完全对应不容易出差错。你不需要推导任何数学公式也不需要担心精度累积误差在某个边界值上引爆问题——因为你的终止条件就是“累加和达到目标”这是定义本身。很多老手可能会说这题还有一个“打表”的做法把 1/2 加到 1/300 的所有前缀和提前算好存进数组然后对每个输入用二分查找定位答案。但说实话对于 POJ 1003 这种输入量不大、上限固定的题打表二分属于“锦上添花”不是必需品。如果你正在练习二分查找那可以顺手用这道题练练手但如果你是第一次接触 OJ老老实实写模拟累加就好。2.3 输入输出的“潜规则”POJ 的输入输出格式要求非常严格。这道题的输入是多行每行一个浮点数直到0.00结束。很多新手在这里容易犯的错是把0.00也当一个普通测试数据去处理结果输出了一行无关的结果。正确的做法是读入一个数后先判断它是否为 0或者与 0 的差值绝对值小于一个极小值如果是就直接结束程序或 continue 到下一轮读取。输出方面每个答案占一行就是一个整数。不要有多余的空格、空行或提示文本。这也是 OJ 题和平时练习的一个重大区别评委只认标准输出你打印的任何额外字符都会被当成答案的一部分进行比对。3. 代码实现三种语言一次讲透3.1 C 语言实现最原汁原味的解法POJ 作为国内老牌 OJ主流提交语言是 C/C。C 语言的实现最贴合题目考察的本意代码如下#include stdio.h int main() { double c; while (scanf(%lf, c) ! EOF) { if (c 0.00) break; double sum 0.0; int n 0; int i 2; while (sum c) { sum 1.0 / i; n; i; } printf(%d card(s)\n, n); } return 0; }注意我这里的写法while (sum c)等于说“只要还没达到就继续累加”循环退出时 sum 一定 c此时 n 正好是第一个满足条件的项数。这里我用了i 2对应题面中的第一项 1/2n 从 0 开始计数每加一项加一次。你也可以直接用n从 1 开始计数然后加1.0 / (n 1)效果是一样的。关于scanf的返回值我写了! EOF这是一个好习惯。虽然题目保证输入以 0.00 结束但加上 EOF 判断可以让程序更健壮避免读取失败时进入死循环。3.2 C 实现输入输出流版本#include iostream using namespace std; int main() { double c; while (cin c) { if (c 0.00) break; double sum 0.0; int n 1; while (sum c) { sum 1.0 / (n 1); n; } cout n - 1 card(s) endl; } return 0; }这个版本我用了n从 1 开始递增累加项为1.0 / (n 1)最后输出n - 1。为什么要减 1因为循环退出条件是sum c在最后一次累加之前 n 已经比实际答案大 1 了。这种“循环变量与答案差一”的情况在算法题里太常见了我推荐初学者在写循环时先用纸笔模拟一遍前几次迭代确认变量关系无误再提交。3.3 Java 实现注意浮点数默认类型import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNextDouble()) { double c sc.nextDouble(); if (c 0.00) break; double sum 0.0; int n 0; int i 2; while (sum c) { sum 1.0 / i; n; i; } System.out.println(n card(s)); } sc.close(); } }Java 的版本与 C 基本一致。唯一需要注意的是 Java 里字面量1.0默认是 double 类型所以1.0 / i得到的是 double不会出现整数除法的问题。如果你不小心写成1 / i结果会直接截断为 0那循环就永远无法满足条件了。这个问题在 C/C 里同样存在必须时刻小心。3.4 代码实现的对比小结语言核心注意点推荐指数Cscanf 返回值判断、浮点数比较极高Ccin 判断、循环变量差一问题极高Java整型除法截断、Scanner 性能高我个人推荐新手先用 C 语言写一遍再用 C 写一遍体会两种风格在输入输出上的差异。尤其是scanf(%lf, c)中lf表示读取 double这一点很多从 Java 转 C 的人会写成%f导致读入异常值。4. 踩坑实录那些让你 WA 到怀疑人生的细节4.1 浮点数判等永远不要直接写c 0.00我在前文代码里写了if (c 0.00)作为结束判断这在 POJ 1003 的数据条件下是能通过的因为题目明确说了输入值是形如0.00、1.00这种精确到小数点后两位的浮点数0 就是精确的 0。但如果你把这段代码推广到其他浮点数输入的场景或者你手动把0.00计算成某个表达式后与 0 比较就会遇到浮点数精度问题。比如0.1 0.2 0.3在绝大多数编程语言中结果是false因为二进制无法精确表示 0.1 和 0.2。在本题中把所有输入都视为“恰好两位小数”的情况下用判断是安全的但为了养成好习惯我建议你写成if (c 1e-9) break; // 或者 fabs(c) 1e-9这样即使输入来自某个计算过程带有极小的浮点误差也能正确识别 0 值。4.2 累加过程中的精度损失为什么答案可能差 1这道题最经典的 WA 原因是这样的你模拟累加在某个边界测试用例比如c 1.00上你的结果是3但标准答案是3没问题换一个用例c 0.50你的结果可能是1也没问题。但到了c 5.20这种接近上限的用例时你可能会得到228而标准答案是227。这是为什么因为题目要求的判定条件是sum c而浮点数累加过程中每一步的加法都会引入微小的舍入误差。如果你从 1/2 一直加到 1/228得到的总和可能比真实数学值小一点点导致你还差最后一丁点才达到 5.20于是多循环了一次。反过来如果你的累加顺序不同比如从大往小加或者每加 10 项重排一次误差方向也可能改变导致结果偏大或偏小。这属于浮点运算的固有特性不是你的代码逻辑错了。那怎么解决几种常见方案给比较公式加上一个极小容差值比如while (sum 1e-9 c)在计算累加和时用 double 而不是 floatfloat 精度太低很容易出问题最稳妥的方案先离线把前缀和算好对每个输入用二分查找找答案。4.3 二分查找方案稳定且优雅打表二分的思路是这样的#include iostream #include vector #include algorithm using namespace std; const int MAXN 300; vectordouble prefix; void init() { double sum 0.0; for (int i 2; i MAXN; i) { sum 1.0 / i; prefix.push_back(sum); } } int main() { init(); double c; while (cin c) { if (c 0.00) break; int ans lower_bound(prefix.begin(), prefix.end(), c) - prefix.begin() 1; cout ans card(s) endl; } return 0; }前缀和数组prefix[k]表示1/2 1/3 ... 1/(k2)也就是“k 张卡片”能伸出的总长度。lower_bound找到第一个不小于 c 的位置加 1 后就是答案。这个方案的优点非常明显前缀和只计算一次后面每次查询都是 O(log n)避开了“多次输入时重复累加”的浪费精度问题可控因为所有前缀和都是在一轮循环中累加出来的不像每次累加从头开始会因计算顺序不同产生微小差异。当然对于这道题来说暴力累加完全够用。但二分打表的思路值得学习因为它在很多“离线查询 静态数据范围”的题目中都是标准优化手段。4.4 输出格式card(s)的坑这道题的输出格式要求是3 card(s)也就是“答案 空格 card(s)”。注意是小写 c、括号、s都要完整且括号是英文半角括号。有些同学会写成Card(s)或者cards全角括号结果 WA 得很冤枉。我在教学中反复强调一句话OJ 是冷血无情的裁判它不看你思路多精妙只看输出字节是否与标准答案完全一致。空格、大小写、换行一个都不能错。5. 延伸思考从 Hangover 到算法思维的养成5.1 为什么题目要设置 5.20 这个上限我在前面提到5.20 大约对应 n 227。为什么 POJ 出题人偏偏选了 5.20 而不是 5.00 或者 10.00我猜测一个原因是如果上限设得太低比如 1.00那答案永远不超过 3题目就没有区分度如果设得太高比如 100.00虽然调和级数发散但 n 会达到 1.5e43double 精度根本撑不住OJ 的测试数据生成也会很麻烦。5.20 这个数值走了一个“能模拟”和“不能模拟”的微妙平衡点——在这个范围内 double 的精度足够保证答案正确同时也考察了选手对浮点数边界问题的敏感度。从题目设计角度看这个上限其实暗示了一条重要信息如果你在代码里尝试用 double 累加超过 10 万项误差可能会累积到你无法接受的程度但在这个题的范围里double 是安全的。所以当你遇到类似题时可以先用直觉估算一下循环次数再决定用什么精度类型。5.2 从一道入门题看 OJ 的“题感”培养很多人觉得 POJ 1003 太简单不值得单独写一篇博文。但我见过太多人在这道题上栽跟头——不是不会做而是不熟悉 OJ 的游戏规则。有的是输出多了空格有的是没处理多组输入有的是用 int 存了 1/2 导致死循环。这些错误背后反映的不是智力问题而是“题感”不足。做题不光是写代码还包括仔细阅读输入输出格式在提交前自己构造边界测试用例用最小用例比如 c0.01和最大用例比如 c5.20各跑一遍确认自己的代码在“多组数据 结束标记”的输入模式下能正确退出。这些习惯一旦养成后面做更复杂的题时会受益无穷。我曾经带过的新人中凡是愿意在入门题上花时间研究边界条件的到了 DP 和图论阶段往往也学得更扎实。5.3 一个值得尝试的变体反向求解你在做完原题后可以顺手思考一个变体如果题目反过来给你一个 n要求输出前 n 项的和保留两位小数怎么做这个变体看似更简单但实际上考察了浮点数格式化输出。C 里可以用printf(%.2lf\n, sum)Java 里可以用System.out.printf(%.2f%n, sum)。你可能会发现输出第 227 项的和时5.20和5.21这种边界值会因舍入规则产生微妙差异。这种“把原题改动一两个变量”的练习方法比盲目刷大量新题更有效。它能让你在相同知识点上反复打磨直到形成肌肉记忆。6. 最终推荐一份可直接提交的“标准答案”最后分享一份我在教学中最常推荐的完整 C 实现思路清晰、边界处理稳妥适合直接提交#include cstdio #include cmath int main() { double c; while (scanf(%lf, c) ! EOF) { if (fabs(c) 1e-9) break; double sum 0.0; int n 0; while (sum 1e-9 c) { n; sum 1.0 / (n 1); } printf(%d card(s)\n, n); } return 0; }代码里的sum 1e-9 c是我个人偏好的写法它给比较留了一个极小的误差窗口又不影响正常数据的判断。你可以去掉1e-9再提交一次大概率也能 AC但保留它能让你的代码在面对刁钻边界数据时更从容。总的来说POJ 1003 Hangover 是一道“门槛低、天花板也不高”的题目但它完美演示了算法竞赛中最核心的三个习惯读题要细、建模要准、边界要想。把这道题吃透你算是正式迈进了 OJ 世界的大门。接下来无论是做 POJ 1004、1005 还是更复杂的题目你都会发现它们都在反复考察这些最基础的能力。本文还有配套的精品资源点击获取