★ FEATURED ARTICLE 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总支数必须等于na ≥ 1b ≥ 1c ≥ 1三种笔都要有a、b、c都是非负整数这是隐藏约束目标函数是让总花费 5a 2b c 最小。这个形式其实就是最基础的整数线性规划只不过它太简单不需要专门的优化算法用贪心就能解决。但“先写数学表达式”这个习惯非常重要。我见过太多人一上来就写代码写到一半才发现自己漏了“每种至少一支”这个约束又回头改浪费时间。把约束和目标分开列出来代码只是把数学翻译成机器语言而已。这里有个生活化类比你去超市买东西预算有限想买的商品种类又多。正常人都会先看单价便宜的多拿点贵的少拿点。买笔也是同样的逻辑——圆珠笔1元最便宜所以应该尽量多买圆珠笔钢笔5元最贵所以应该尽量少买钢笔。这个直觉方向是对的但光有直觉不够要能证明它。1.3 为什么答案不是“平均分配”很多人刚看到“三种笔都要买”这个条件第一反应是把n平均分成三份比如n6时买2支钢笔、2支铅笔、2支圆珠笔。这个方案满足约束总花费是5×22×21×216元。但直接买1支钢笔、1支铅笔、4支圆珠笔总花费是52411元。同样买6支笔后者便宜了5元差距非常大。为什么会差这么多因为三种笔的单价差异太大了。钢笔和铅笔的成本是圆珠笔的5倍和2倍平均分配等于强行让贵笔和便宜笔数量一样多完全没考虑价格因素。题目要的是“总花费最少”不是“数量平均”所以目标函数决定了我们必须优先选择单价低的笔。再做一个极端测试n100平均分配大约是33、33、34总花费接近33×533×234×1265元。而正确答案是1支钢笔、1支铅笔、98支圆珠笔总花费5298105元。差了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”特别容易写错很多人只算后面的自由分配忘了保底那支也算进圆珠笔数量里。用n6验证1支钢笔、1支铅笔、4支圆珠笔总花费52411元总支数1146符合要求。比平均分配的16元少5元证明这个方案是当前约束下的最优解。2.2 用反证法证明“贪心策略”成立算法题不能只说“我觉得这样最优”要能给出让人信服的理由。这里可以用反证法。假设存在一个最优方案其中钢笔数量a≥2。那么我从这个方案里拿掉1支钢笔换成1支圆珠笔。总支数不变因为去掉1支再加1支三种笔仍然都有因为钢笔从a变成a-1如果a≥2换完后钢笔至少还有1支不违反约束。但是总花费减少了5-14元这比原方案更便宜说明原方案不是最优的。矛盾。同理如果铅笔数量b≥2拿掉1支铅笔换成1支圆珠笔总花费减少2-11元也能得到一个更优方案。所以最优方案里钢笔和铅笔都不能超过1支。再结合“每种至少1支”它们必须正好等于1支。剩下的n-2支全部是圆珠笔这就是唯一最优解。这段证明就是教材把它放在“选择结构”章节的原因之一题目本身不需要循环但需要你用if区分边界情况同时培养“先证明后编码”的思维。很多学生能猜出答案但说不清为什么到后面学贪心算法、动态规划时就会吃亏因为那些题靠猜是猜不出来的。2.3 边界条件n1和n2怎么处理这是这道题真正的分水岭。题目要求三种笔都至少买1支那么n至少是3。如果输入的n是1或者2数学上无解。一本通原题对这种情况通常约定输出固定提示比如“No solution”或者按要求输出特定内容。但也有OJ会保证测试数据n≥3不需要你额外判断。保险的做法是无论题目有没有说都在代码里加上边界判断。原因很简单你不判断n1时程序会输出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钢笔铅笔圆珠笔总支数总花费31113861146111001198100105n3是合法最小值答案只有一种可能1、1、1花费8元。n6验证了我前面说的“平均分配反例”正确方案花费11元。n100验证公式在大数值下依然成立圆珠笔占绝大多数。如果你还不放心可以自己写一个暴力枚举程序把所有可能的钢笔、铅笔数量都试一遍用循环找出最小花费的那个方案然后和贪心答案对比。这个技巧叫“对拍”后面我会专门讲怎么写。3.3 另一种常见题面给n元钱买尽可能多的笔我在前面提到过网上搜“买笔”还会看到另一版本输入n表示金额钢笔5元、铅笔2元、圆珠笔1元要求三种都买问最多能买多少支以及各买几支。这个版本同样先保证每种至少1支花掉8元剩下n-8元全部买1元的圆珠笔。答案变为钢笔1支、铅笔1支、圆珠笔n-7支最多能买n-5支笔。验证n9时先买钢笔1支、铅笔1支、圆珠笔1支花8元剩1元再买1支圆珠笔共买4支。按公式圆珠笔n-72支总支部数n-54支正确。这两个版本非常容易混淆因为题面都叫“买笔”价格也一样。区分方法就看输入变量名如果题目说“要买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比较大时这个两重循环会很慢但它可以作为验证工具。比如n100时循环次数大约是5000次瞬间出结果n10000时循环次数约5000万次会有点卡但也不至于跑不出来。用暴力程序的输出和贪心程序对比如果一致说明贪心在这个数据点上是正确的。4. 常见错误与排查技巧实录4.1 漏掉“每种至少一支”这是最典型的错误。有人直接输出0、0、n也就是全部买圆珠笔总花费n元。表面看确实最便宜但题目明确要求三种笔都要买。这个错误在样例里尤其容易暴露因为样例往往会选一个很小的n比如n3输出0、0、3就明显不对。检查方法很简单看输出里有没有0。只要出现0就违反“每种至少一支”的约束。写代码时我习惯把约束条件写成注释放在最前面// 约束1 钢笔 n-21 铅笔 n-钢笔-11 圆珠笔这样每次看到注释就会提醒自己不要漏掉约束。4.2 边界条件没判断圆珠笔数量变成负数如果n2直接计算圆珠笔n-20已经违反“圆珠笔至少1支”如果n1圆珠笔-1直接输出负数。这类错误在OJ上通常表现为“答案错误”或者“运行时错误”因为负数数量没有任何实际意义。解决办法就是前面写的先判断n是否小于3是则输出无解提示。不要觉得“题目肯定会给合法数据”实测下来很多OJ的隐藏测试就喜欢放边界值你不判断就WA。4.3 输出顺序与题目要求不一致有些题要求输出“圆珠笔、铅笔、钢笔”有些要求“钢笔、铅笔、圆珠笔”。同一道题在不同OJ上描述可能不同所以不要拿上一道题的输出顺序硬套。这个错误的隐蔽性在于当n3时输出“1 1 1”和“1 1 1”没有区别样例根本测不出来。但n4时正确输出“1 1 2”如果你输出“2 1 1”OJ就会判错。排查技巧在IDE里用多组数据手测特别是n3、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支”。讲不清楚说明还没真正吃透。最后说点个人体会。这道题我在不同场合讲过很多遍每次都会让学员先说答案再写代码。大部分人说“圆珠笔最便宜所以多买圆珠笔”方向是对的但只有少数人能补上“每种至少一支”这个关键约束。教这道题时我会特意追问一句“如果n2怎么办”能答上来的人说明真的把分支结构用在了点子上。后面学更复杂的贪心、动态规划这种“先找约束再定目标最后写代码”的顺序才是这道题真正想教会我们的东西。它看起来只是买几支笔实际上是在帮你建立一种思考模型——任何最优方案问题都值得先停下来问一问什么是最便宜的什么是必须买的什么限制条件会让答案发生变化。能把这几个问题想清楚比多刷十道重复题都有用。
阅读完成 · 觉得有帮助？
