有时候最“简单”的题反而最容易在奇怪的地方翻车。比如题号2059这道“买笔”一看就是入门教材第三章里的分支结构例题题干总共一句话小明拿着n元钱去买笔钢笔5元一支圆珠笔2元一支铅笔1元一支要求正好把钱花完并且买到的笔总数尽量少问三种笔各买多少支。刚学完if语句的同学都会觉得这有什么难的结果一提交WA得莫名其妙。今天我就把这道题从题干到代码、从思路到对拍完整拆一遍。先说清楚这篇适合谁看如果你刚学到选择结构正在刷分支题如果你要带竞赛班需要给新手讲明白“按余数分类讨论”到底是怎么回事哪怕你纯粹想搞清楚自己为什么会错都能往下看。整道题的知识点其实就三个整除和取余、if/switch分支、以及一点点贪心直觉。当然代码实现也不是随便写几个判断就完事里面有几个坑尤其是余数为4的时候十个人里至少有五个会写错。1. 原题信息题干、数据约定与输出要求1.1 常见题干描述我按最主流的版本来说。小明有n元钱文具店里三种笔的价格分别是钢笔5元一支圆珠笔2元一支铅笔1元一支。要求钱必须正好花完不能找零也不能剩钱同时买到手的笔总数要尽可能少最后输出钢笔、圆珠笔、铅笔各买了多少支。这里“总数尽可能少”是关键。为什么要买得少可以理解成老师要发奖品预算固定希望奖品数量少一点、档次高一点说白了就是把钱花在单价高的东西上。正因为目标是件数最少解题方向才是优先买贵的东西整套思路都围绕这一点展开。如果题目改成“总数尽可能多”那解法就全变了后面我会在变体部分专门说。1.2 数据范围与输出约定n在多数OJ上是正整数范围一般不超过10000但也有一些题目会把n改大到10的18次方级别。所以代码里最好直接用long long而不是int。很多新手觉得这题简单int够用了结果数据一放大直接就溢出属于完全可以避免的翻车。输出一般是三个整数用空格隔开顺序默认是钢笔、圆珠笔、铅笔。有的题面会说“若有多组解输出任意一组”这句话基本可以忽略因为这个模型下达到“总数最少”的方案基本是唯一的至少本解法给出的方案不会踩到多解判定的问题。1.3 题目背后真正想考的三个点这道题放在第三章目的就是练分支结构。具体来说考了三件事第一整数除法n/5和取余n%5的使用。所有分情况讨论都建立在“先买钢笔再看剩多少钱”这个操作上。第二if-else if或者switch的分支能力。不同余数对应不同的补买策略漏掉任何一种都会WA。第三也是最容易被忽略的贪心思想的萌芽。想要件数少就要优先买单价高的钢笔余数部分优先用单价第二高的圆珠笔去凑。这三个点正好是后续很多贪心和动态规划题的雏形。别觉得这题简单它其实是后面一大片题目的“种子”。2. 先想清楚再写代码余数分类是这道题的灵魂2.1 优先买钢笔为什么不是猜的总钱数固定想让买的笔数量最少直觉上就应该优先买最贵的那一种。一支钢笔5元顶5支铅笔的名额所以同样一笔钱全买钢笔时件数一定最少。设钢笔数量为x圆珠笔数量为y铅笔数量为z并且满足5x2yzn。所有方案的总件数是xyz。稍微做一个变形xyz xy(n-5x-2y) n-4x-y也就是说想让总件数最小等价于让4xy最大。那x为什么不干脆一直加因为5元一支钢笔2元一支圆珠笔如果减少1支钢笔省下来的5元最多能换2支圆珠笔这时4xy的变化是-42-2反而变小了总件数变多。如果换出来的圆珠笔少于2支那件数增加得更多。所以最优方案里钢笔数量一定是n/5也就是在预算内尽量多买钢笔。这一步推明白之后题目就变成先买n/5支钢笔剩下的钱是n%5余数范围只能是0到4接下来只需要针对这5种余数分别处理。2.2 五种余数逐一拆解余数为0也就是n正好是5的倍数那还有什么好说的全部买钢笔零圆珠笔零铅笔。余数为1。比如n11先买2支钢笔花掉10元剩1元。1元不够买圆珠笔只能再买1支铅笔。于是答案是钢笔2支圆珠笔0支铅笔1支。余数为2。比如n12先买2支钢笔花掉10元剩2元。这2元可以买1支圆珠笔也可以买2支铅笔明显买1支圆珠笔的件数更少。答案是钢笔2支圆珠笔1支铅笔0支。余数为3。比如n13剩3元。方案有两个1支圆珠笔加1支铅笔一共2件或者3支铅笔一共3件。选前者答案是钢笔2支圆珠笔1支铅笔1支。余数为4。重点来了比如n14剩4元。这里最容易犯的错是写成“1支圆珠笔加2支铅笔”一共3件但事实上还可以买2支圆珠笔一共2件。2比3小所以正确答案是圆珠笔2支铅笔0支。记住余数4对应的是两支圆珠笔而不是“一支圆珠笔加两支铅笔”。这五种情况整理成表格就是这样n % 5圆珠笔数量铅笔数量说明000全部买钢笔101剩1元只能买铅笔2101支圆珠笔优于2支铅笔311比3支铅笔少1件420比“1圆珠笔2铅笔”少1件2.3 其实可以总结成一个更短的规律看这张表圆珠笔数量其实就是r除以2的商铅笔数量是r除以2的余数。也就是说r3时3除以2商1余1r4时4除以2商2余0。这个规律让代码有了第二种写法直接套公式。但我不建议初学者跳过分支直接写公式。分支版本的逻辑非常直白每一行都对应一个实际场景错了容易定位公式版虽然短但前提是你已经把五种情况彻底理解了。比赛里代码短确实能省时间可前提是心里有底。2.4 一个常见理解误区有人会问余数为1时能不能把一支钢笔换成1支圆珠笔加3支铅笔然后让总数更少答案是不能。随便算一个数比如n16最优方案是3支钢笔加1支铅笔总共4件如果把其中1支钢笔换成1支圆珠笔和3支铅笔就变成2支钢笔、1支圆珠笔、4支铅笔总共7件数量反而暴增。这道题和“买得越多越好”的题目有一个本质区别单价高是优势拆开只会让件数变多。所以在“总数最少”的前提下钢笔一支都不能拆所有操作都发生在买完钢笔之后的余数里。3. 两种代码实现if-else if与switch选哪个3.1 if-else if版本这是最基础、也最适合初学的写法。每一条分支对应表里的一行逻辑清清楚楚#include bits/stdc.h using namespace std; int main() { long long n; cin n; long long a n / 5; // 钢笔数量 long long b 0, c 0; // 圆珠笔、铅笔 int r n % 5; if (r 0) { b 0; c 0; } else if (r 1) { b 0; c 1; } else if (r 2) { b 1; c 0; } else if (r 3) { b 1; c 1; } else { // r 4 b 2; c 0; } cout a b c endl; return 0; }读代码的时候注意一点r是n%5的余数n本身很大但余数只有0到4这个范围所以用int存r完全没问题。a、b、c这三个数量就可能很大了所以用long long。3.2 switch版本C里面对“一个整数有多个固定取值”的情形switch通常比一长串else if更清爽。因为五种情况本质上是在对数字做“查表”switch的case结构天然贴合这种需求#include bits/stdc.h using namespace std; int main() { long long n; cin n; long long a n / 5; long long b 0, c 0; switch (n % 5) { case 0: b 0; c 0; break; case 1: b 0; c 1; break; case 2: b 1; c 0; break; case 3: b 1; c 1; break; case 4: b 2; c 0; break; } cout a b c endl; return 0; }用switch有一个很容易踩的坑每个case结尾的break不能丢。忘了break的话程序会继续执行下一个case那结果就有意思了比如余数1会跑到余数2的分支里稳稳WA。所以我的建议是初学阶段先用if-else if因为漏写else的概率比漏写break低等对switch的流程控制非常熟悉了再用它来缩短代码。3.3 精简公式版如果你已经完全理解前面的推导其实整个分支可以压缩成两行long long b (n % 5) / 2; long long c (n % 5) % 2;这就是我前面说的规律圆珠笔数量是余数除以2的整数部分铅笔数量是余数除以2的余数部分。代码会很短但我不建议在刚学分支结构时这么写。原因很简单公式版一旦出错你很难通过代码本身定位问题而if-else if版每一步都是直译题目错了看一眼就知道是哪一行。3.4 为什么强调long long如果你在OJ上看到的这道题n范围只有10000那用int确实不会出问题。但我遇到过一些改编版本n能到10的18次方这时候n/5在int里直接就溢出了。写题养成习惯涉及可能变大的整数一律long long能省去很多不必要的RE和WA。别觉得这是小题大做一组题错一次就长记性了。4. 对拍验证用小规模暴力枚举给你的代码上一道保险4.1 暴力枚举的思路分支代码写完了怎么确认它对最可靠的方法不是自己脑测几个样例而是写一个“笨办法”程序把钢笔、圆珠笔的所有数量都枚举一遍铅笔数量用剩余的钱去凑然后找出总件数最小的方案。这个方法虽然慢但正确性非常直观完全不需要动脑。枚举范围也好控制钢笔最多n/5支圆珠笔最多n/2支枚举完x和y之后铅笔数就是n-5x-2y只要这个数不小于0就是一种合法方案。4.2 完整的对拍程序把分支解法封装成一个可比较的对象然后让n从1跑到200每一步都和暴力结果比较一旦不一致就立刻报警#include bits/stdc.h using namespace std; void brute(long long n, long long ga, long long gb, long long gc) { long long bestCnt LLONG_MAX; for (long long x 0; x n / 5; x) { for (long long y 0; y n / 2; y) { long long z n - 5 * x - 2 * y; if (z 0) continue; long long cnt x y z; if (cnt bestCnt) { bestCnt cnt; ga x; gb y; gc z; } } } } int main() { for (long long n 1; n 200; n) { long long a1 n / 5; long long b1, c1; int r n % 5; if (r 0) { b1 0; c1 0; } else if (r 1) { b1 0; c1 1; } else if (r 2) { b1 1; c1 0; } else if (r 3) { b1 1; c1 1; } else { b1 2; c1 0; } long long a2, b2, c2; brute(n, a2, b2, c2); if (a1 ! a2 || b1 ! b2 || c1 ! c2) { cout mismatch at n n endl; return 0; } } cout all ok endl; return 0; }如果屏幕上输出all ok那么至少对n从1到200的所有情况你的分支代码和暴力结果完全一致。这一步做完代码的正确性就有了一个非常扎实的验证。4.3 对拍的习惯要趁早培养很多初学者觉得对拍是搞难题才需要的操作其实恰恰相反。越是看起来简单的题越容易因为“自己以为对”而写上错答案而且这种错误往往用一两个样例发现不了。对拍程序写一次不到五分钟但能让你在大量数据范围内确认思路正确性价比极高。我后来做贪心题、搜索题只要思路有半点不确定第一反应就是写个暴力对拍而不是继续盯着屏幕干想。5. 从这道题延伸出去买多、改价、以及更一般的“找零”模型5.1 变体一要求总数最多每种笔至少买一支如果题目改成“总数尽可能多”甚至设置了“每种笔都必须买至少一支”的附加条件思路就完全反过来了。总数多想让件数多就要优先买最便宜的铅笔但每种至少一支的约束会强迫你各买一支钢笔和圆珠笔。做法是先硬性买1支钢笔加1支圆珠笔加1支铅笔总共花掉8元剩下n-8元全部拿来买铅笔。比如n20就是钢笔1支、圆珠笔1支、铅笔11213支总件数15。注意这种写法有个前提n要大于等于8否则无法满足“每种至少一支”题目一般会保证数据合理但写代码时心里要有数。5.2 变体二价格参数不再是5、2、1如果钢笔、圆珠笔、铅笔的价格换成a、b、c三个数并且abc那“先尽量买最贵的钢笔再利用余数分类”的策略就不一定继续成立了。比如价格是4、3、1n6时贪心先买一支4元的钢笔剩下2元买两支1元铅笔总件数3但正确最优方案是买两支3元的圆珠笔总共2件。所以这类题要老老实实枚举或者做动态规划。这种做法思路是枚举圆珠笔数量y然后看剩余的钱怎么用钢笔和铅笔凑。n比较小的时候甚至可以直接三重循环把所有组合都过一遍。虽然不优雅但能保证正确对新人来说也没什么丢人的。5.3 从分支走向更通用的硬币问题其实“买笔”本质上是这样一个模型给你面额1、2、5三种硬币问凑出n元最少需要多少枚硬币。在这个特定面额组合下贪心成立所以一道分支题就能解决。但当面额变成1、3、4时贪心就会出错你需要的是动态规划。学习路线可以这样走先用这道题掌握分支和余数分类然后思考“为什么贪心在这里成立”最后再去接触完全背包或最短路形式的找零问题。你会发现当年那个让你一个字母一个字母敲if的“买笔”原来是一个里程碑。最后说点实际的这道题我当年第一次做的时候就在余数为4的地方翻过车顺手写了“1支圆珠笔加2支铅笔”样例过了提交WA后来用暴力枚举对拍才发现应该买2支圆珠笔。从那以后我对“看起来显然对”的代码都多留了一个心眼。给你一个特别实用的自测小技巧提交前在本地把n等于10、11、12、13、14、15、19这几个值全部跑一遍。10对应余数011对应余数112对应余数213对应余数314和19对应余数415又是一个整除。这几个数字能覆盖所有分支只要它们都输出正确代码基本就稳了。分支结构就是这样代码永远不难写难的是你有没有把每一种情况都真正想过一遍。