做深基2顺序结构这一章的时候P5709 这道苹果和虫子大概是很多人第一次栽跟头的地方。题面短得不像话三个整数进、一个整数出样例也就两行看上去就是个小学除法题。但真正提交之后你就会发现这题的通过率并没有想象中那么友好有人样例全过却拿到 RE有人结果差一个数拿到 WA还有人明明写的是数学上正确的公式却在某一组极端数据上翻了车。\n\n这道题的核心价值不在于算法有多难而在于它把三个非常典型的编程基本功塞进了一个极小的场景里除零保护、向上取整的语义判断、结果边界的钳制。这三样东西在你后面写分页、写装箱、写时间片调度的时候都会反复出现。所以我把这道题的完整思路、三种语言的可提交代码以及我自己从 RE 改到 AC 的全过程整理出来适合刚学完输入输出和分支语句、正在刷洛谷深基系列的同学也适合想拿它当课堂例题的老师和家长。1. 先把题面读三遍苹果、虫子和那句容易被忽略的完整1.1 输入输出格式与数据范围一句话说清题目给出三个非负整数分别是苹果总数 m、吃完一个苹果需要花费的分钟数 t、以及已经过去的时间 s。要求输出一个整数表示现在还剩下多少个完整的苹果。数据范围是 m 在 1 到 100 之间t 在 0 到 100 之间s 在 1 到 10000 之间。这三个范围都小得可怜小到你可以直接用循环一分钟一分钟地模拟也可以毫秒级地用一行公式算完。但也正因为范围小出题人很容易在边界上做文章——比如那个0 ≤ t它不是一个多余的写法而是整道题最大的一个陷阱后面我会专门拆开讲。另外要注意输入是一行三个数、用空格分隔不是三行。别看这个细节小我见过不止一个同学因为用了cin m; cin t; cin s;之外的奇怪读入方式比如读整行再去切分字符串结果被行尾的\r或者多余空格坑到而白白调试半小时。既然格式是空格分隔的三个整数就直接用最朴素的输入方式别炫技。1.2 完整的苹果这四个字才是本题的题眼很多人读题的时候会把注意力放在吃一个要 t 分钟上然后顺手写出s / t这样的除法。问题就出在这里题目问的不是吃掉了多少个而是剩下多少个完整的。这两个说法的差别在哪里举个具体的例子。假设 t 5s 4。也就是说吃一个苹果需要 5 分钟而现在只过去了 4 分钟。按照吃掉了多少个来理解4 分钟连一个都没吃完吃掉的数量应该是 0。但按照剩下多少个完整的来理解这 4 分钟里那个人已经开始啃第一个苹果了虽然没啃完但这个苹果已经被咬过了它显然不能再算作完整的苹果。所以正确的数量关系是只要开始吃一个苹果这个苹果就从完整变成了不完整。换句话说消耗掉的苹果数量等于时间 s 被 t 分成多少段、并且向上取整。用数学符号写就是吃掉的数量 ⌈s / t⌉最后剩下的完整苹果数 m − ⌈s / t⌉。把上面那个例子代进去⌈4 / 5⌉ 1吃掉一个剩下 m − 1 个。这个理解方式如果你第一遍读题就能抓住这道题基本就赢了一半。1.3 为什么它叫 Prologue这个系列在铺垫什么题目英文名叫 Apples ProloguePrologue 是序章、前传的意思。也就是说这只是苹果和虫子这个主题的开场题后面还有正片。开场题的任务从来不是难住你而是把后面会反复用到的几个基础动作先练熟一是把生活语言翻译成数学表达式二是处理取整方向这种语义模糊带来的偏差三是养成看数据范围、找边界的习惯。我个人的建议是做这类序章题的时候不要满足于 AC而是顺手问自己三个问题这题如果 t 的范围放宽到 10^9 会怎样如果 s 也变得很大、乘法会不会溢出如果要求输出被吃掉的苹果数而不是剩下的完整苹果数代码要改哪一行能答上这三个问题你的收获会比单纯刷十道同类型的题还大。2. 三个能让判题机给你 WA 和 RE 的细节2.1 t 等于 0除零带来的 RE 与死循环数据范围里写着0 ≤ t这个 0 不是摆设。它的现实含义是吃一个苹果不需要花任何时间也就是可以瞬间把所有苹果吃完。这时候答案显然是 0因为 m 个苹果在 0 秒内就被清空了。但如果你不加判断直接写s / t或者(s t - 1) / t程序在做整数除法时就会出现除以零。在 C 里整数除以零是未定义行为实际提交到评测机上通常表现为运行时错误RE有时候表现为输出一个垃圾值总之不会是 AC。Java 里整数除以零会抛出 ArithmeticExceptionPython 里会抛 ZeroDivisionError三个语言的报错形式不同但结果都一样挂。用循环模拟的写法也一样有坑。如果你写成while (time s) { time t; eaten; }那么当 t 0 的时候time 0永远不会让 time 超过 s于是死循环最后 TLE。所以不管你是用公式还是用模拟t 0 都必须在最前面单独拦掉。if (t 0) { printf(0\n); return 0; }提示这道题里 t 0 时答案恒为 0因为它和 m、s 的取值无关。这种某个参数取特殊值就让整个问题退化的情况是编程题里最常见的边界考点养成条件反射式地先扫一遍输入范围的习惯能省下大量调试时间。2.2 向上取整还是向下取整差一个苹果就是 WA我在前面说了答案是 m − ⌈s / t⌉。这里的取整方向是向上你要在代码里明确地表达出来。很多人的第一反应是写m - s / t这在 s 恰好能被 t 整除的时候是对的一旦除不尽就少算了一个被啃过的苹果。举个能立刻看出差别的例子m 10t 3s 7。3 分钟吃一个7 分钟过去了。前 3 分钟吃完第一个第 4 到第 6 分钟吃完第二个第 7 分钟开始吃第三个但还没吃完。所以完整的苹果是 10 − 3 7 个。如果用s / t算7 / 3 2整数除法向下取整得到 10 − 2 8答案就多了 1WA。这里还有一个容易混淆的点很多人会想第三个苹果都没吃完凭什么算它被吃掉了。这里的关键在于题目问的是完整的苹果没吃完的苹果已经不完整了所以它必须从答案里扣掉。判断依据不是吃完与否而是是否已经开始吃。把这一层语义想通了向上取整就是唯一正确的选择。2.3 结果不能为负max(0, ...) 不是可选项再考虑一种情况m 5t 4s 10000。按照公式算⌈10000 / 4⌉ 2500吃掉的数量远远超过苹果总数那么 5 − 2500 −2495。这个负数显然不是合法答案实际的物理含义是苹果早就吃完了还剩下的完整苹果数是 0。所以最后一步必须对结果做下限钳制取max(0, m - eaten)。这一步在数学上看起来有点多余但在程序里是必须的因为题目问的是还有多少个完整的苹果而不是按公式计算出来的差值。差值为负意味着苹果吃完了剩下 0 个仅此而已。注意这个坑非常隐蔽因为很多人测试的时候用的都是 m 比较大、s 比较小的数据结果永远为正压根想不到还有负数这种情况。评测机的数据里一定会有 m 很小而 s 很大的用例专门用来卡这一点。3. 从 while 循环到一行公式三种解法的取舍3.1 最不容易错的模拟写法如果你刚学完循环对取整公式还不太有把握完全可以老老实实地模拟。思路很直白时间是分钟一格一格往前走的每走满 t 分钟就消耗一个苹果直到时间用完或者苹果吃完为止。为了避免 t 0 时死循环前面还是要特判。#include cstdio int main() { int m, t, s; scanf(%d %d %d, m, t, s); if (t 0) { printf(0\n); return 0; } int eaten 0, used 0; while (used t s eaten m) { used t; eaten; } // 注意如果时间没用完但已经开始吃下一个那个也要算 if (used s eaten m) eaten; printf(%d\n, m - eaten); return 0; }这段代码里有几个细节值得说。循环条件用used t s而不是used s是为了区分刚好在某一分钟吃完和还差一点没吃完这两种情况。循环结束之后如果used s说明时间还有剩余、而且苹果还没吃完那就意味着当前正在啃的那个苹果已经开始吃了必须再补一个计数。你会发现这种模拟写法虽然直观但边界条件反而更多、更容易写错。所以模拟适合用来验证公式而不是作为最终提交的版本。3.2 整数向上取整的三种写法与边界验证整数除法天生是向下取整的要实现向上取整常见的有三种写法我们逐个看它们的安全性和可读性。写法表达式适用条件风险点加法和除法(s t - 1) / tt 0t 0 时除零除法加取余s / t (s % t ! 0)t 0可读性稍差减一再加一(s - 1) / t 1s 0 且 t 0s 0 时需要单独处理第一种(s t - 1) / t是最常用的写法也是我个人最推荐的。它的原理是如果 s 能被 t 整除那么加上 t − 1 之后仍然不会跨过下一个整数倍除下来结果不变如果不能整除加上 t − 1 就会把它顶到下一个整数倍上除下来正好多 1。用两组数据验证一下s 6t 3则 (6 2) / 3 8 / 3 2和 6 / 3 2 一致s 7t 3则 (7 2) / 3 9 / 3 3比 7 / 3 2 多了 1正确。第二种写法s / t (s % t ! 0)更容易理解但要注意s % t ! 0在 C 里是布尔值参与运算时会隐式转成 0 或 1某些编译器会给出警告写的时候最好显式加个? 1 : 0。第三种写法在 s 0 的时候会算出 0但本题 s ≥ 1所以其实也安全只是通用性差一点。溢出问题在这道题里不用担心s 最大 10000t 最大 100s t − 1 最多 10099int 完全装得下。但如果你以后做的是数据范围到 10^18 的题s t - 1就有可能超出 long long那时候就要改用s / t (s % t ! 0)这种不会额外放大的形式了。这种当前数据范围安全、但要把习惯养对的意识是我觉得比 AC 本身更值钱的东西。3.3 C、Python、Java 三份可直接提交的代码同一个思路在三个语言里的表达略有不同尤其是整数除法和最大值的写法我把它整理出来方便你对照。C 版本#include cstdio #include algorithm int main() { int m, t, s; scanf(%d %d %d, m, t, s); if (t 0) { printf(0\n); return 0; } int eaten (s t - 1) / t; printf(%d\n, std::max(0, m - eaten)); return 0; }Python 版本m, t, s map(int, input().split()) if t 0: print(0) else: eaten (s t - 1) // t print(max(0, m - eaten))Python 里要特别注意除以零的判断位置如果写成eaten (s t - 1) // t之后再判断程序会直接抛异常什么都输出不了。另外 Python 的//是向下取整的整除配合(s t - 1)同样能得到向上取整的结果。Java 版本import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(), t sc.nextInt(), s sc.nextInt(); if (t 0) { System.out.println(0); return; } int eaten (s t - 1) / t; System.out.println(Math.max(0, m - eaten)); return; } }Java 的int整数除法同样是截断取整对正数来说就是向下取整逻辑和 C 一致。类名必须是Main这一点写过 Java 题目的同学应该都清楚。4. 我自己的提交记录从 RE 到 AC 的完整排查链路4.1 第一次提交样例过了评测机上 RE我第一次写这道题的时候代码大概是这样读入三个数直接用s / t算吃掉的数量然后输出m - s / t。本地跑样例两个样例都对我很自信地提交结果评测机返回的结果让我愣了一下Runtime Error。当时的排查过程是这样的我把这条链路完整写出来希望对你以后的调试有帮助。第一步确认是哪种 RE。我把代码在本地用几个极端输入跑了一遍包括1 0 1、1 0 10000、100 0 1在 t 0 的那一组上程序直接崩了。到这一步基本可以定位除以零。第二步确认这个 RE 是不是评测数据触发的。因为 t 的范围明确写着可以取 0那评测数据里必然会有 t 0 的用例所以这不是偶然是我漏掉了题面给我的信息。第三步改代码。在最前面加一行if (t 0)的特判输出 0 并直接返回。这时候再提交RE 消失了但出现了新的问题有一个测试点 WA。第四步找 WA 的原因。这就回到了取整方向的问题。我把s / t改成向上取整(s t - 1) / t再提交WA 的点变了说明我改对了一部分但还有问题。第五步继续缩小范围。剩下的 WA 只出现在 m 很小、s 很大的用例上。我构造了5 4 10000这组数据手算了一下发现结果是负数。加上max(0, ...)的钳制之后终于 AC。整个过程花了我大概四十分钟但收获是实打实的一道题的三次修改其实对应了三类完全不同的错误类型——运行期错误、语义理解错误、边界处理错误。能把这三种错误分清楚以后调试的时候就不会一通乱改。4.2 我自己整理的边界自测表从那次之后我养成了一个习惯每做一道有参数范围的题就自己列一张边界表在提交前手动跑一遍。这道题我整理的表是这样的输入m t s预期输出考察点10 3 77除不尽时的向上取整1 1 10刚好吃完最后一个5 4 200时间恰好是整数倍5 4 210吃完了还要继续吃结果不能为负3 0 1000t 0 的特殊情况1 100 11开始吃但没吃完100 100 100000极限数据这张表里我特意放了1 100 1这一组。它的含义是只有一个苹果吃它要 100 分钟现在过了 1 分钟。按照开始吃就不完整的理解这个苹果已经不算完整了答案是 0。如果你写的是吃完了才计数的逻辑就会输出 1这组数据能精准地把这两种理解区分开。提示自己造数据比等评测机告诉你答案效率高得多。特别是这种小范围的题你完全可以在草稿纸上把边界全列出来花五分钟手算一遍比反复提交省时间。4.3 提交页偶发的无法解析路由对象提示怎么处理顺便聊一个和题目本身无关、但很多同学会遇到的小状况提交代码的时候页面偶尔会弹出提交失败、无法解析路由对象之类的提示看起来像是代码被判定有问题其实完全不是。这类提示通常是页面层面的问题跟你的代码一点关系都没有。我遇到过的几种情况和处理方式是这样的登录状态过期在页面上停留时间太长会话已经失效这时候提交请求会被拦下来。处理方式很简单刷新页面重新登录一次把代码再粘一遍提交就行。前端脚本没加载完网络波动导致提交按钮绑定的脚本还没就绪你点得太快请求就没发出去。多等两秒再点或者重新进一次题目页。浏览器缓存或插件干扰某些广告拦截类插件会误伤提交请求。可以试着用无痕窗口打开或者临时关掉插件。页面开了多个标签页同一个题目页开了好几个互相之间可能有状态冲突。关掉多余的只留一个再提交。另外提醒一句遇到这种情况不要反复疯狂点提交按钮有时候请求其实已经发出去了重复点会导致同一份代码提交两次反而让提交记录看起来很乱。判断方法是刷新一下提交记录页面看看是不是已经有一条记录了。5. 把这道题当模板取整类问题的通用处理思路5.1 向上取整公式的通用形态这道题真正想教给你的东西其实是如何把每 X 个一组、剩下不足一组也算一组这个语义翻译成整数运算。这个模式在编程里出现的频率高得惊人我把它的通用形态写出来如果有 n 个单位需要按每组 k 个进行分组且不足一组的部分也算一组那么组数 ⌈n / k⌉ (n k − 1) / kk 0。把这个公式带回本题n 就是经过的时间 sk 就是吃一个苹果需要的分钟数 t组数就是被吃掉的苹果数量。你会发现题目和公式是一一对应的只是换了个苹果的皮。识别出这层对应关系你以后遇到类似的题就不需要重新推导了。需要留意的是这个公式的前提k 必须大于 0。所以在用之前一定要先确认分母的取值范围如果可以取 0就必须像本题一样单独处理。我见过太多人在这一步栽跟头写出来的时候逻辑完全正确就是忘了范围里的那个 0。5.2 相同模型的四个生活场景为了让你对这个模式更有感觉我把它在四个不同场景里的应用列一下。这些场景看起来风马牛不相及但底层的数学结构完全一样。分页显示一共 1000 条记录每页显示 20 条问需要多少页。答案是 (1000 20 − 1) / 20 50 页。如果换成 1001 条就是 51 页最后那页只有 1 条但仍然算一页。装箱发货90 件商品每个箱子最多装 12 件需要多少个箱子。答案是 (90 12 − 1) / 12 8 个箱子最后一个箱子装不满。班车排班400 名乘客每辆车坐 45 人需要几辆车。答案是 (400 45 − 1) / 45 9 辆车。任务时间片一批任务总共需要 700 毫秒系统每次调度 16 毫秒需要多少个时间片。答案是 (700 16 − 1) / 16 44 个。这四个场景里只要出现不足一份也算一份这个语义向上取整就是标准答案。反过来如果语义是不足一份就丢掉那才轮得到向下取整。判断取整方向的关键永远是先搞清楚题目怎么处理那个不完整的部分而不是凭直觉写除法。5.3 做完这题之后该练什么如果你这道题已经 AC 了我建议下一步不要急着跳到更难的算法而是先把取整 边界这个组合练透。深基2 这一章后面还有好几道题会用到相邻的思路比如用除法和取余来拆分一个整数的各位数字、把秒数换算成时分秒之类它们的共同特点都是用数学运算代替循环。再往后的顺序结构章节里会出现需要处理浮点数精度、需要比较大小取最值、需要做简单分段计算的题。这些题目本身都不难但每一道都会埋一两个边界陷阱比如负数除法、浮点误差、极端输入。我的经验是每做完一道题都顺手写一遍这题如果参数取到边界值会怎样的推演坚持二十道题之后你会发现自己在提交前就能预判出哪些数据可能挂这种手感是刷题量本身堆不出来的。最后分享一个我一直在用的小习惯每道 AC 之后我会把自己踩过的坑用一句话记在题目旁边比如这道题记的就是t 可以为 0除法前先特判结果要 max(0, ...)。下次遇到同类型的题扫一眼这句话就能避开九成的重复错误。