2059：【例3.11】买笔，这道题我相信学过信息学奥赛的同学都不陌生。它是《信息学奥赛一本通》第三章选择结构部分的经典例题，题目讲的是买笔这件事——钢笔5元一支、铅笔2元一支、圆珠笔1元一支，要求三种笔都至少买一支，在给定总支数的条件下让总花费最少。我第一次见到它时觉得太简单了，答案一眼就能看出来，但后来带学生刷题才发现，越是这种看起来简单的题，越能暴露出对边界条件和最优策略理解不到位的问题。这篇文章不打算只贴一段代码，而是从题目建模、数学推导、边界判断到扩展变式，完整走一遍。适合刚学完if语句、准备刷一本通例题的初学者，也适合想给学员讲清楚“为什么是这个答案”的教练朋友。
1. 题目理解与思路拆解
1.1 题面与输入输出
先说最常见的题面版本：输入一个整数n，表示老师要买的笔总数。钢笔每支5元，铅笔每支2元，圆珠笔每支1元。要求钢笔、铅笔、圆珠笔三种笔都至少买1支，并且让总花费尽量少。输出三个整数，分别表示钢笔、铅笔、圆珠笔的数量。
这里有一个非常容易踩坑的点：题目输入的是“总支数n”，不是“总钱数”。很多第一次做这道题的同学，看到价格就默认输入的是钱，然后按照“我有n元钱，怎么买最多”去解，结果跟标准答案完全对不上。所以拿到题的第一步永远是确认变量含义——输入到底是数量还是金额，输出顺序是什么。不同OJ的题面细节可能有差异，有的版本是“给n元钱，买尽可能多的笔”，那个答案会不一样，后面我会单独讲。当前这版，请记住：n是笔的总支数。
数据范围方面，一本通原题通常给的n不大，int足够。但为了稳妥，建议直接使用long long，因为在扩展题面里n可能到10^9甚至更大，int在21亿左右就会溢出，用long long不用重新思考。反正这类题目用long long没有额外成本。
1.2 把“买笔”翻译成数学表达式
题目读懂了，下一步是建模。设钢笔a支、铅笔b支、圆珠笔c支。那么题目给出的约束条件是：
- a + b + c = n，总支数必须等于n；
- a ≥ 1，b ≥ 1，c ≥ 1，三种笔都要有；
- a、b、c都是非负整数，这是隐藏约束；
- 目标函数是让总花费 5a + 2b + c 最小。
这个形式其实就是最基础的整数线性规划，只不过它太简单，不需要专门的优化算法，用贪心就能解决。但“先写数学表达式”这个习惯非常重要。我见过太多人一上来就写代码，写到一半才发现自己漏了“每种至少一支”这个约束，又回头改，浪费时间。把约束和目标分开列出来，代码只是把数学翻译成机器语言而已。
这里有个生活化类比：你去超市买东西，预算有限，想买的商品种类又多。正常人都会先看单价，便宜的多拿点，贵的少拿点。买笔也是同样的逻辑——圆珠笔1元最便宜，所以应该尽量多买圆珠笔，钢笔5元最贵，所以应该尽量少买钢笔。这个直觉方向是对的，但光有直觉不够，要能证明它。
1.3 为什么答案不是“平均分配”
很多人刚看到“三种笔都要买”这个条件，第一反应是把n平均分成三份，比如n=6时买2支钢笔、2支铅笔、2支圆珠笔。这个方案满足约束，总花费是5×2+2×2+1×2=16元。但直接买1支钢笔、1支铅笔、4支圆珠笔，总花费是5+2+4=11元。同样买6支笔，后者便宜了5元，差距非常大。
为什么会差这么多？因为三种笔的单价差异太大了。钢笔和铅笔的成本是圆珠笔的5倍和2倍，平均分配等于强行让贵笔和便宜笔数量一样多，完全没考虑价格因素。题目要的是“总花费最少”，不是“数量平均”，所以目标函数决定了我们必须优先选择单价低的笔。
再做一个极端测试：n=100，平均分配大约是33、33、34，总花费接近33×5+33×2+34×1=265元。而正确答案是1支钢笔、1支铅笔、98支圆珠笔，总花费5+2+98=105元。差了160元，够再买160支圆珠笔了。所以这道题虽然简单，但“按直觉平均分配”就是最大的错误方向。
2. 从数学推导到分支结构
2.1 先固定“每种至少一支”的保底方案
既然每种笔都至少要买1支，那我们可以把问题拆成两个部分：保底的3支 + 剩下的n-3支。
保底部分必须买1支钢笔、1支铅笔、1支圆珠笔，花费8元。这3支是硬性约束，无论如何都要花。剩下的n-3支就自由了，可以全部选择单价最低的圆珠笔，因为每多买一支圆珠笔，成本只有1元；买铅笔要2元，买钢笔要5元。
所以答案直接就是：钢笔1支、铅笔1支、圆珠笔n-2支。注意圆珠笔是1支保底加上后面n-3支，总共n-2支，不是n-3支。这个“n-2”特别容易写错，很多人只算后面的自由分配，忘了保底那支也算进圆珠笔数量里。
用n=6验证：1支钢笔、1支铅笔、4支圆珠笔，总花费5+2+4=11元，总支数1+1+4=6，符合要求。比平均分配的16元少5元，证明这个方案是当前约束下的最优解。
2.2 用反证法证明“贪心策略”成立
算法题不能只说“我觉得这样最优”，要能给出让人信服的理由。这里可以用反证法。
假设存在一个最优方案，其中钢笔数量a≥2。那么我从这个方案里拿掉1支钢笔，换成1支圆珠笔。总支数不变，因为去掉1支再加1支；三种笔仍然都有，因为钢笔从a变成a-1，如果a≥2，换完后钢笔至少还有1支，不违反约束。但是总花费减少了5-1=4元，这比原方案更便宜，说明原方案不是最优的。矛盾。
同理，如果铅笔数量b≥2，拿掉1支铅笔换成1支圆珠笔，总花费减少2-1=1元，也能得到一个更优方案。所以最优方案里，钢笔和铅笔都不能超过1支。再结合“每种至少1支”，它们必须正好等于1支。剩下的n-2支全部是圆珠笔，这就是唯一最优解。
这段证明就是教材把它放在“选择结构”章节的原因之一：题目本身不需要循环，但需要你用if区分边界情况，同时培养“先证明后编码”的思维。很多学生能猜出答案，但说不清为什么，到后面学贪心算法、动态规划时就会吃亏，因为那些题靠猜是猜不出来的。
2.3 边界条件：n=1和n=2怎么处理
这是这道题真正的分水岭。题目要求三种笔都至少买1支，那么n至少是3。如果输入的n是1或者2，数学上无解。
一本通原题对这种情况通常约定输出固定提示，比如“No solution”或者按要求输出特定内容。但也有OJ会保证测试数据n≥3，不需要你额外判断。保险的做法是：无论题目有没有说，都在代码里加上边界判断。原因很简单，你不判断，n=1时程序会输出1、1、-1，圆珠笔数量是负数，一看就不合理。虽然OJ数据不一定测得到，但这个习惯能避免很多隐藏问题。
分支结构在这里的表达方式：
if (n < 3) { cout << "No solution" << endl; } else { cout << 1 << " " << 1 << " " << n - 2 << endl; }这个if就是整道题唯一的“算法”。你说它简单吗？确实简单。但能把边界判断写对、能把输出格式写对、能解释清楚为什么这样写，比代码本身更重要。
3. 实操过程：代码实现与验证
3.1 C++完整代码与逐行说明
下面给出完整代码，我加了注释，方便初学者逐行对照。
#include <iostream> using namespace std; int main() { // n 表示需要购买的笔的总支数 long long n; cin >> n; // 边界处理：三种笔每种至少1支，所以 n 必须至少为3 if (n < 3) { cout << "No solution" << endl; return 0; } // 最优方案：钢笔1支，铅笔1支，剩余全部买圆珠笔 long long gang = 1; // 钢笔数量 long long qian = 1; // 铅笔数量 long long yuan = n - 2; // 圆珠笔数量 // 输出顺序：钢笔、铅笔、圆珠笔 cout << gang << " " << qian << " " << yuan << endl; // 下面这行可以用于自测时输出总花费，实际提交时记得注释掉 // cout << "total = " << 5 * gang + 2 * qian + yuan << endl; return 0; }逐行说明一下。long long是为了防止n比较大时int溢出。if (n < 3)处理无解情况。真正计算只有一行yuan = n - 2。最后输出时，注意题目要求的是“钢笔、铅笔、圆珠笔”的顺序，不要随手写成yuan << qian << gang，这个错误非常隐蔽，样例可能测不出来，但大数据对比时就会WA。
我在实际教学中发现，很多学员提交代码报错后，最容易忽略的就是输出顺序。建议在写输出语句前先把题目里的要求抄在注释里，比如// 输出：钢笔 铅笔 圆珠笔，这样不容易搞混。
3.2 三组手算验证，确保答案可靠
写完代码不能直接交，至少要手算几组数据。我习惯选边界值、普通值、较大值各一组：
| n | 钢笔 | 铅笔 | 圆珠笔 | 总支数 | 总花费 |
|---|---|---|---|---|---|
| 3 | 1 | 1 | 1 | 3 | 8 |
| 6 | 1 | 1 | 4 | 6 | 11 |
| 100 | 1 | 1 | 98 | 100 | 105 |
n=3是合法最小值，答案只有一种可能：1、1、1，花费8元。n=6验证了我前面说的“平均分配反例”，正确方案花费11元。n=100验证公式在大数值下依然成立，圆珠笔占绝大多数。
如果你还不放心，可以自己写一个暴力枚举程序，把所有可能的钢笔、铅笔数量都试一遍，用循环找出最小花费的那个方案，然后和贪心答案对比。这个技巧叫“对拍”，后面我会专门讲怎么写。
3.3 另一种常见题面：给n元钱，买尽可能多的笔
我在前面提到过，网上搜“买笔”还会看到另一版本：输入n表示金额，钢笔5元、铅笔2元、圆珠笔1元，要求三种都买，问最多能买多少支，以及各买几支。
这个版本同样先保证每种至少1支，花掉8元，剩下n-8元全部买1元的圆珠笔。答案变为：钢笔1支、铅笔1支、圆珠笔n-7支，最多能买n-5支笔。
验证：n=9时，先买钢笔1支、铅笔1支、圆珠笔1支，花8元，剩1元再买1支圆珠笔，共买4支。按公式，圆珠笔n-7=2支，总支部数n-5=4支，正确。
这两个版本非常容易混淆，因为题面都叫“买笔”，价格也一样。区分方法就看输入变量名：如果题目说“要买n支笔”，走第一种；如果题目说“有n元钱”，走第二种。我强烈建议拿到题先圈出“n支”还是“n元”，这个动作能避免大量无谓的WA。
3.4 暴力枚举写法，用来验证贪心答案
下面这段暴力代码并不需要提交，它是用来验证思路的。比赛和练习时，我经常先写出贪心解法，再用暴力程序对拍，确认答案一致后才提交。
#include <iostream> #include <climits> using namespace std; int main() { long long n; cin >> n; long long bestG = 0, bestQ = 0, bestY = 0; long long bestCost = LLONG_MAX; // 钢笔至少1支，最多n-2支；铅笔至少1支，最多n-钢-1支 for (long long g = 1; g <= n - 2; g++) { for (long long q = 1; q <= n - g - 1; q++) { long long y = n - g - q; if (y < 1) continue; long long cost = 5 * g + 2 * q + y; if (cost < bestCost) { bestCost = cost; bestG = g; bestQ = q; bestY = y; } } } cout << bestG << " " << bestQ << " " << bestY << endl; cout << "total = " << bestCost << endl; return 0; }当n比较大时，这个两重循环会很慢，但它可以作为验证工具。比如n=100时，循环次数大约是5000次，瞬间出结果；n=10000时，循环次数约5000万次，会有点卡，但也不至于跑不出来。用暴力程序的输出和贪心程序对比，如果一致，说明贪心在这个数据点上是正确的。
4. 常见错误与排查技巧实录
4.1 漏掉“每种至少一支”
这是最典型的错误。有人直接输出0、0、n，也就是全部买圆珠笔，总花费n元。表面看确实最便宜，但题目明确要求三种笔都要买。这个错误在样例里尤其容易暴露，因为样例往往会选一个很小的n，比如n=3，输出0、0、3就明显不对。
检查方法很简单：看输出里有没有0。只要出现0，就违反“每种至少一支”的约束。写代码时我习惯把约束条件写成注释放在最前面：
// 约束：1 <= 钢笔 <= n-2，1 <= 铅笔 <= n-钢笔-1，1 <= 圆珠笔这样每次看到注释，就会提醒自己不要漏掉约束。
4.2 边界条件没判断，圆珠笔数量变成负数
如果n=2，直接计算圆珠笔n-2=0，已经违反“圆珠笔至少1支”；如果n=1，圆珠笔=-1，直接输出负数。这类错误在OJ上通常表现为“答案错误”或者“运行时错误”，因为负数数量没有任何实际意义。
解决办法就是前面写的：先判断n是否小于3，是则输出无解提示。不要觉得“题目肯定会给合法数据”，实测下来很多OJ的隐藏测试就喜欢放边界值，你不判断就WA。
4.3 输出顺序与题目要求不一致
有些题要求输出“圆珠笔、铅笔、钢笔”，有些要求“钢笔、铅笔、圆珠笔”。同一道题在不同OJ上描述可能不同，所以不要拿上一道题的输出顺序硬套。
这个错误的隐蔽性在于：当n=3时，输出“1 1 1”和“1 1 1”没有区别，样例根本测不出来。但n=4时，正确输出“1 1 2”，如果你输出“2 1 1”，OJ就会判错。
排查技巧：在IDE里用多组数据手测，特别是n=3、4、5这类小数据，把输出结果和题目要求的顺序逐项对照。我还会把题目原文复制到注释里，输出前再读一遍，成本低、效果好。
4.4 用浮点数计算金额
有的同学习惯写成5 * a + 2 * b + c，这没问题。问题在于有人会用浮点数：
double cost = 5.0 * a + 2.0 * b + c;然后判断cost == 某个值。金额都是整数，浮点数比较容易出现精度问题，比如0.1 + 0.2不等于0.3。在买笔这道题里，直接全部用整数计算和比较，既准确又高效。看到钱、数量、人数这类题目，优先用int或long long，不要引入double。
4.5 对拍技巧：用暴力程序当裁判
我强烈建议从这道题开始养成对拍习惯。所谓对拍，就是写一个正确但可能很慢的暴力程序，和一个快速但需要验证的贪心程序，用随机数据反复跑，比较两者输出。
具体步骤：写两个程序，一个存为greedy.cpp，一个存为brute.cpp；再写一个生成随机数据的程序gen.cpp；最后用脚本循环调用这三个程序，发现输出不一致就停下来检查。
这道题生成随机数据很简单：随机生成一个n，范围从1到1000。贪心答案和暴力答案在任何合法的n上都应该完全一致。如果有一天你对某道贪心题心里没底，这个对拍流程能救命。平时练习时多写暴力程序，也能加深对题目约束的理解，算是百利无一害的习惯。
5. 从“买笔”延伸出的思维工具
5.1 贪心策略成立的条件
买笔问题本质是一个贪心模型：单价越低的笔越应该多买，直到约束条件把它拦住。这里的约束是“每种至少1支”，所以钢笔和铅笔各1支就被拦住了，剩下的全部给最便宜的圆珠笔。
贪心策略只有在满足特定条件时才成立，不是所有题目都能这么干。比如要求“三种笔数量之差不能超过1”，那答案就完全不一样了。所以做题时一定要先确认：这个问题的局部最优选择，是否真的能拼出全局最优？买笔问题可以，因为它没有“后效性”——前面怎么选不会影响后面剩余数量的约束，每支笔的选择互不干扰。
我在课上经常用一个类比：贪心就像去自助餐厅，如果所有菜随便拿、价格都一样，那你肯定先拿自己最爱吃的。但如果规定“每道菜必须至少拿一勺”，你就得先拿一遍，再把最喜欢的多拿几勺。买笔就是这个逻辑。
5.2 如果价格改成其他值，贪心还成立吗
这里我补充一个容易混淆的点。假设价格改成钢笔5元、铅笔3元、圆珠笔1元，答案仍然是钢笔1、铅笔1、圆珠笔n-2，因为价格从低到高的顺序没变，圆珠笔依然最便宜。但如果价格改成钢笔4元、铅笔3元、圆珠笔2元，答案依然是钢笔1、铅笔1、圆珠笔n-2，因为圆珠笔依然最便宜。
关键在于“单价排序”而不是“具体价格”。只要最便宜的笔没有数量上限、没有额外限制，优先买它通常都是对的。但注意，一旦出现“圆珠笔最多只能买x支”这类限制，贪心就不能简单套了，需要复杂一点的讨论。我们做题时要能识别这种变化。
5.3 相似练习题推荐
这道题的价值在于，把它弄懂之后，同一类型的题目可以批量解决。比如“买铅笔”“分练习本”“买糖果”等，很多都是换了个物品名称、换了几个价格，核心逻辑完全一样。再往后学，还会碰到“找零钱问题”“最少硬币问题”，这些是买笔问题的进阶版，区别在于硬币的数量可能有上限，或者需要考虑金额不能恰好凑整的情况。
刷题顺序上，我建议先保证能把这道题的推导过程默写出来，再去做一本通第三章后面的分支结构题目。不要满足于“跑通了样例”，要能闭着眼睛讲清楚“为什么钢笔和铅笔各1支、圆珠笔n-2支”。讲不清楚，说明还没真正吃透。
最后说点个人体会。这道题我在不同场合讲过很多遍，每次都会让学员先说答案再写代码。大部分人说“圆珠笔最便宜，所以多买圆珠笔”，方向是对的，但只有少数人能补上“每种至少一支”这个关键约束。教这道题时，我会特意追问一句：“如果n=2怎么办？”能答上来的人，说明真的把分支结构用在了点子上。后面学更复杂的贪心、动态规划，这种“先找约束，再定目标，最后写代码”的顺序，才是这道题真正想教会我们的东西。它看起来只是买几支笔，实际上是在帮你建立一种思考模型——任何最优方案问题，都值得先停下来问一问：什么是最便宜的，什么是必须买的，什么限制条件会让答案发生变化。能把这几个问题想清楚，比多刷十道重复题都有用。
