1. 项目概述与核心需求解析最近在带学生准备信息学奥赛信奥的刷题遇到了一道很有意思的题目——P6188 [NOI Online #1 入门组] 文具订购。这道题乍一看是个简单的数学问题但深入下去会发现它完美地融合了枚举、条件判断、贪心与优化思想是检验C基础算法能力和逻辑严谨性的绝佳试金石。很多刚接触信奥的同学一看到“订购文具”就觉得是小学数学题结果一上手写代码就漏洞百出要么超时要么答案不对。今天我就结合自己多年的刷题和教学经验把这道题的“里子”和“面子”都拆开来讲透让你不仅能把题做对更能理解背后通用的解题思维。题目核心是这样的小明要花光手头的n元钱去订购三种文具圆规每个7元、笔每支4元、笔记本每本3元。设购买数量分别为a,b,c他的订购原则有严格的优先级首要目标最优先a b c尽可能大。也就是说在花光钱的前提下买的物品总件数要最多。次要目标在第一目标满足的前提下a尽可能大。即在总件数最多的所有方案中要选择购买圆规数量最多的那个。最终目标在前两个目标都满足的前提下b尽可能大。也就是在总件数最多、且圆规数量也最多的方案里选择买笔数量最多的方案。如果没有任何一种购买组合能恰好花光n元则输出-1。否则输出满足上述所有条件的a,b,c。这题的难点在于它不是一个简单的求最大值问题而是一个带有多重约束条件的优化问题。你不能只盯着一个变量看必须系统地遍历所有可能并按照严格的优先级规则进行筛选。这非常考验对循环控制、条件判断和逻辑排序的理解。2. 解题思路拆解从暴力枚举到策略优化面对这类问题新手最容易想到的就是三重循环暴力枚举让a,b,c分别从0开始循环直到7*a 4*b 3*c n为止然后检查是否等于n并记录满足条件的方案。这个方法直观但效率极低。假设n是10^5这个量级三层循环的复杂度是 O(n³)绝对会超时Time Limit Exceeded, TLE。所以我们必须优化。核心思路是减少循环层数和尽早剪枝。2.1 思路一基于圆规数量的两重循环推荐这是最清晰、最常用的优化方法。我们注意到圆规最贵7元。既然题目要求a圆规数量在总件数最多的前提下尽可能大我们可以从大到小枚举a。为什么是从大到小因为我们的次要目标是让a尽可能大。如果我们从小到大枚举找到了一个总件数最多的方案但它的a可能不是最大的。而从大到小枚举a我们就能保证一旦我们以某个a为基准找到了总件数最多的方案那么这个a就是当前可能的最大值后续更小的a就不用再考虑总件数是否更大了因为a已经变小了即使总件数一样多优先级也不如当前方案。具体步骤设max_a n / 7这是圆规数量的理论上限。让a从max_a循环到0。对于每一个固定的a计算剩余金额rest n - 7*a。接下来在剩余金额rest下我们需要用笔4元和笔记本3元来花光钱并且使得b c尽可能大因为a已固定总件数abc最大等价于bc最大。在这个子问题里我们还要让b尽可能大。对于固定的a和rest我们可以用两重循环枚举b和c但这样还是 O(n²)。可以进一步优化枚举b计算c。b的范围是0到rest / 4。对于每个b计算remain rest - 4*b。如果remain % 3 0则说明可以全部买笔记本花光此时c remain / 3。这样就得到了一个候选方案(a, b, c)。我们需要在所有候选方案中按照题目优先级选择最优解。由于a是从大到小枚举的我们只需要维护一个“当前最优解”。比较规则是如果当前方案的(abc)大于 已记录最优解的(abc)则更新最优解。如果(abc)相等则比较aa大的更优。如果a也相等则比较bb大的更优。c不需要比较因为当a, b, abc都确定时c是确定的。这个方法的复杂度降到了大约 O(n * (n/4))对于n 10^5是可行的。但还可以继续优化枚举b的过程。2.2 思路二利用模运算进一步优化枚举在上面的步骤5中我们枚举b来求c。观察方程4*b 3*c rest。我们可以从模运算的角度思考。对于方程4b 3c m其中m rest我们想找到非负整数解(b, c)使得bc最大且在bc最大的前提下b最大。一个经典的贪心思路是因为笔记本更便宜3元在总金额固定时买更多的笔记本理论上能增加总件数。但这里有个限制金额必须恰好花光。我们可以这样处理让c从可能的最大值开始尝试。c的最大值是m / 3。令c m / 3然后检查m - 3*c是否能被4整除即是否能用来买笔。如果能就得到一组解。如果不能就让c减1再检查直到c减到0。这样我们找到的第一个解就是满足bc最大的解因为c从大到小试并且由于c在减小b在增加我们找到解时b也是当前bc固定下的最大值。这个内层循环的复杂度从 O(n) 降到了 O(1) 到 O(3) 之间因为c最多调整3次因为 3 和 4 互质在模4的意义下调整步长是3的模4逆元相关实际上最多尝试4次就能判断是否有解。这样整体复杂度就优化到了 O(n)非常高效。注意这里涉及到一个数论小知识对于不定方程4b 3c m其有非负整数解的充要条件是m可以被gcd(4,3)1整除这总是成立的。但我们要找的是满足特定优化目标的解。上述“c从大到小尝试”的方法是一个有效的贪心策略并且容易理解和实现。2.3 思路三动态规划DP可行性分析有同学可能会想这像个完全背包问题是的我们可以把问题转化为总容量为n有三种物品体积分别为7、4、3价值分别为1因为我们要最大化物品数量。但这不仅仅是最大化价值还有第二、第三优先级a和b最大。这需要我们在DP状态里额外记录物品的选择信息并在状态转移时进行复杂的比较。对于此题DP的状态设计和转移比较繁琐代码不如枚举法直观且时间复杂度也是 O(n)但常数可能更大。因此在竞赛中思路二优化枚举通常是首选它思维直接代码简洁效率足够。3. 核心代码实现与逐行解析我们采用**思路二优化枚举**来实现。代码将分为几个函数以提高可读性。3.1 辅助函数求解给定剩余金额下的最优 (b, c)这个函数解决子问题已知剩余金额m求非负整数b,c满足4*b 3*c m且优先级为1.bc最大2.b最大。// 函数返回一个pairbool, pairint, int // 第一个bool表示是否有解 // 第二个pair中的两个int分别代表b和c pairbool, pairint, int solve_bc(int m) { // 从c可能的最大值开始尝试 int max_c m / 3; for (int c max_c; c 0; --c) { int remaining m - 3 * c; if (remaining 0 remaining % 4 0) { int b remaining / 4; // 找到的第一个解就是最优解 // 1. 因为c从大到小所以bc在当前c下是最大的b(m-3c)/4。 // 2. 对于固定的bcc越小b越大。我们是从c最大开始减所以找到解时b是当前bc下的最大值。 return {true, {b, c}}; } // 一个小优化如果remaining已经小于0其实可以提前结束但这里循环条件保证了c0remaining不会小于0。 // 另一个优化因为4和3互质循环最多进行4次就能判断。但写成for循环更清晰。 } return {false, {0, 0}}; // 无解 }实操心得这里为什么c从max_c开始往下减我们来验证一下贪心正确性。我们的目标是bc最大。假设有两个解(b1, c1)和(b2, c2)且c1 c2。由于4b3cm是固定的如果c更大那么4b就更小所以b就更小。那么b1c1和b2c2哪个大不一定。但我们的枚举策略是从最大的c开始这意味着我们优先尝试让便宜的物品笔记本尽可能多。对于固定的m物品单价越低能买的数量上限越高。从c最大开始尝试一旦找到一个可行的b那么此时的bc就是对于这个c值所能达到的最大bc因为b被唯一确定。我们无法直接证明这个解就是全局最优但可以这样思考如果存在另一个解(b, c)使得bc bc那么由于c max_c并且我们的循环是从max_c向下我们会先遇到c吗不一定。但可以证明在c从大到小的遍历中第一个找到的解的bc值一定是所有解中最大的。因为如果存在更大的bc那么对应的c要么更大但c最大就是max_c要么更小。如果c更小那么当我们的循环到c时计算出的b会更大bc也会更大这就会更新我们的解。实际上这个循环遍历了所有可能的c并计算了对应的b然后我们通过比较来记录最优解。为了简单我们在函数内不进行比较而是在主函数中对于每个a调用此函数得到一组(b,c)然后与当前最优解比较。这样逻辑更清晰。让我们修正一下这个函数让它只负责寻找是否存在解并返回其中一个解例如通过上述方法找到的。最优解的判断放在主函数中因为需要和不同的a产生的解进行比较。// 修正版寻找方程 4b3cm 的一组非负整数解。 // 返回一个pairbool, pairint, intbool表示是否有解。 pairbool, pairint, int find_bc_solution(int m) { // 简单的枚举c for (int c m / 3; c 0; --c) { int rem m - 3 * c; if (rem 0 rem % 4 0) { return {true, {rem / 4, c}}; } } return {false, {0, 0}}; }这个函数就是找到一个解不保证是bc最大的也不保证是b最大的。但主函数中我们会对每个a调用它如果找到解我们就得到了一个候选方案(a, b, c)。然后我们拿这个方案去和当前记录的最优方案按照题目的三个优先级规则进行比较。因为a是从大到小枚举的所以当总件数更多时我们会更新最优解当总件数一样时由于a是从大到小枚举后面遇到的a更小所以不会更新当总件数和a都一样时我们需要比较b。因此我们需要在比较规则中完整实现这三个优先级。3.2 主函数逻辑与最优解比较#include iostream using namespace std; // 上面定义的 find_bc_solution 函数放在这里 int main() { int n; cin n; int best_a -1, best_b -1, best_c -1; int best_total -1; // 用于记录最优解的总件数初始为-1便于比较 // 枚举圆规数量a从大到小 for (int a n / 7; a 0; --a) { int rest n - 7 * a; auto [has_solution, bc] find_bc_solution(rest); if (has_solution) { int b bc.first; int c bc.second; int total a b c; // 与当前最优解比较 bool update false; if (best_a -1) { // 还没有最优解直接更新 update true; } else if (total best_total) { // 优先级1总件数更大 update true; } else if (total best_total) { if (a best_a) { // 优先级2总件数相同a更大 update true; } else if (a best_a) { if (b best_b) { // 优先级3总件数和a都相同b更大 update true; } } } if (update) { best_a a; best_b b; best_c c; best_total total; } // 注意这里不能break因为即使当前a找到了解但可能更大的a虽然当前循环是从大到小a就是当前最大找到的解总件数更多吗 // 我们需要继续检查更小的a因为更小的a可能会让出钱来买更多的笔和笔记本从而导致总件数(bc)增加可能抵消a的减少后总件数依然更大。 // 例子n14。a2时rest0b0,c0,total2。a1时rest7找不到4b3c7的解。a0时rest14解为b2,c2,total4。 // 显然a0的总件数更大。所以我们必须枚举所有a。 } } if (best_a -1) { cout -1 endl; } else { cout best_a best_b best_c endl; } return 0; }关键点解析枚举顺序a从n/7向下枚举到0。这保证了我们优先考虑圆规多的方案。比较逻辑这是本题的核心。update标志的判定条件严格对应了题目的三个优先级。必须注意else if的顺序这体现了优先级的层次。不能提前退出循环这是新手极易出错的地方。即使当前a找到了一个解也不能break因为更小的a可能会产生总件数(abc)更多的解。我们必须在所有a中寻找总件数最大的解。优先级一的地位高于优先级二。初始值best_a -1作为一个无效状态标志比用0更安全因为a0可能是一个有效解。3.3 代码优化与完善上面的代码逻辑正确但find_bc_solution函数对于每个a都可能循环m/3次在最坏情况下a0时mn内层循环是 O(n) 的整体复杂度是 O(n²)对于n10^5可能有点悬10^10次操作。我们需要实现之前提到的优化版find_bc_solution利用模运算将内层复杂度降到常数。优化思路对于4b 3c m我们考虑m除以4的余数。令m % 4 r(r 0, 1, 2, 3)。方程左边4b是4的倍数所以3c除以4的余数必须等于r。计算3c % 4的值c0时余0c1时余3c2时余2c3时余1。所以3c % 4会循环出现。因此对于给定的r我们可以快速找到满足3c % 4 r的最小非负整数c。然后检查m - 3c是否非负且能被4整除。由于3和4互质c在0~3之间一定能找到一个解如果原方程有解。找到这个c后b (m - 3c) / 4。但我们的目标不仅是找到任意解而是找到满足优先级bc最大然后b最大的解。在4b3cm的约束下b和c是此消彼长的。要bc最大直觉上应该让便宜的物品笔记本3元尽可能多即c尽可能大。但c最大不一定能使bc最大因为b会变小。我们需要找到使bc最大的解。有一个数学性质对于不定方程4b3cm其通解可以表示为如果有一组特解(b0, c0)那么所有整数解可以写成(b0 3k, c0 - 4k)k为整数。我们要找的是非负整数解且使bc最大。bc (b0c0) - k。所以为了最大化bc我们需要最小化k。在非负整数解的限制下b03k 0且c0-4k 0。所以k的取值范围是-b0/3 k c0/4。为了最小化k我们取k为这个范围内最小的整数。通常我们可以先找到一组特解然后通过调整k来找到最优解。对于竞赛编程一个更简单且高效的方法是枚举c除以4的余数。因为b和c的关系受模4约束。我们可以直接枚举c的四种可能余数0,1,2,3计算出对应的c和b然后从中选优。优化后的find_bc_solution函数返回满足优先级的最优解pairbool, pairint, int find_optimal_bc(int m) { int best_b -1, best_c -1; int best_sum -1; // 枚举c模4的余数 for (int r 0; r 4; r) { // 我们需要 c % 4 r并且 3c % 4 m % 4 (因为 4b % 4 0) // 但更直接的方法我们枚举的是c的余数计算对应的c和b // 设 c 4 * t r, t 0 是整数。 // 则 4b m - 3*(4tr) m - 12t - 3r // b (m - 3r)/4 - 3t // 要使b为非负整数需要 (m - 3r) 0 且 (m - 3r) % 4 0。 // 令 base (m - 3r) / 4则 b base - 3t, c 4t r。 // 我们需要 b 0 且 c 0即 base - 3t 0 t base/3。 // 同时 t 0。 // 现在总件数 bc (base - 3t) (4t r) base r t。 // 为了最大化 bc我们需要最大化 t。t 最大为 floor(base / 3)。 // 但还要注意当 t 取最大值时b 可能为0或正数。 if (m 3 * r (m - 3 * r) % 4 0) { int base (m - 3 * r) / 4; // 当t0时的b值 int max_t base / 3; // t的最大值 // 我们取 t max_t以获得最大的 bc int t max_t; int b base - 3 * t; int c 4 * t r; // 验证非负性 if (b 0 c 0) { int sum b c; if (sum best_sum || (sum best_sum b best_b)) { best_sum sum; best_b b; best_c c; } } } } if (best_b -1) { return {false, {0, 0}}; } else { return {true, {best_b, best_c}}; } }这个函数稍微复杂一些但它是 O(1) 的。它枚举了c的四种余数情况对于每种情况直接计算出了能使bc最大的t即c中完整的4的组数从而得到了在该余数下的最优解然后再在所有余数的最优解中根据bc和b的优先级选出全局最优解。将主函数中的find_bc_solution调用替换为find_optimal_bc整个算法的时间复杂度就降为了 O(n)对于n高达10^5也游刃有余。4. 完整AC代码与测试样例结合以上所有优化我们给出最终的高效AC代码。#include iostream using namespace std; // 寻找在金额m下满足4b3cm的最优解(b,c)优先级bc最大 - b最大 pairbool, pairint, int find_optimal_bc(int m) { int best_b -1, best_c -1; int best_sum -1; // 记录最大的bc // 枚举c模4的余数r (0,1,2,3) for (int r 0; r 4; r) { // 条件1: m - 3r 0 (保证基础金额非负) // 条件2: (m - 3r) % 4 0 (保证b是整数) if (m 3 * r (m - 3 * r) % 4 0) { int base_b (m - 3 * r) / 4; // 当c中不包含完整的4的倍数时的b值即t0 // 设 c 4t r, b base_b - 3t // 需要 b 0 - t base_b / 3 int max_t base_b / 3; // 为了最大化 bc (base_b - 3t) (4t r) base_b r t我们取最大的t int t max_t; int b base_b - 3 * t; int c 4 * t r; // 由于t取最大值b可能为0或正数c肯定非负 if (b 0) { // 已经保证了c0 int sum b c; // 按照优先级比较先比sum再比b if (sum best_sum || (sum best_sum b best_b)) { best_sum sum; best_b b; best_c c; } } } } if (best_b -1) { return {false, {0, 0}}; } else { return {true, {best_b, best_c}}; } } int main() { int n; cin n; int best_a -1, best_b -1, best_c -1; int best_total -1; // 枚举a从大到小 for (int a n / 7; a 0; --a) { int rest n - 7 * a; auto [has_solution, bc] find_optimal_bc(rest); if (has_solution) { int b bc.first; int c bc.second; int total a b c; // 严格按照题目优先级比较 if (best_a -1) { best_a a; best_b b; best_c c; best_total total; } else if (total best_total) { best_a a; best_b b; best_c c; best_total total; } else if (total best_total) { if (a best_a) { best_a a; best_b b; best_c c; best_total total; } else if (a best_a b best_b) { best_b b; best_c c; // best_a和best_total不变 } } } } if (best_a -1) { cout -1 endl; } else { cout best_a best_b best_c endl; } return 0; }测试样例与解析样例输入114解析钱是14元。a2花14元买2个圆规rest0find_optimal_bc(0)返回b0, c0总件数2。a1花7元rest74b3c7无解。a0花0元rest14find_optimal_bc(14)需要计算。枚举rr0: m140, (14-0)%42!0跳过。r1: m3成立(14-3)%411%43!0跳过。r2: m6成立(14-6)%48%40成立。base_b8/42。max_t2/30。t0。b2, c2。sum4。r3: m9成立(14-9)%45%41!0跳过。最优解是b2, c2, sum4。总件数abc0224。比较a0的方案总件数4 a2的方案总件数2所以最优解是(0, 2, 2)。预期输出0 2 2样例输入21解析钱是1元连最便宜的笔记本3元都买不起更别说凑整花光了。所有a枚举后都无解。预期输出-1样例输入333解析这是一个复杂的例子可以用来验证优先级。a4rest33-2854b3c5解为b?, c?。枚举rr0: (5-0)%45%41!0r1: 53成立(5-3)%42%42!0r2: 56不成立r3: 59不成立。无解。a3rest33-21124b3c12。r0: (12-0)%40, base_b3, max_t3/31, t1, b0, c4, sum4。r1: (12-3)%49%41!0r2: (12-6)%46%42!0r3: (12-9)%43%43!0。最优解b0, c4, sum4。总件数3047。a2rest33-14194b3c19。r0: (19-0)%43!0r1: 193, (19-3)%416%40, base_b4, max_t4/31, t1, b1, c5, sum6。r2: 196, (19-6)%413%41!0r3: 199, (19-9)%410%42!0。最优解b1, c5, sum6。总件数2158。a1rest33-7264b3c26。r0: (26-0)%42!0r1: 263, (26-3)%423%43!0r2: 266, (26-6)%420%40, base_b5, max_t5/31, t1, b2, c6, sum8。r3: 269, (26-9)%417%41!0。最优解b2, c6, sum8。总件数1269。a0rest334b3c33。r0: (33-0)%41!0r1: 333, (33-3)%430%42!0r2: 336, (33-6)%427%43!0r3: 339, (33-9)%424%40, base_b6, max_t6/32, t2, b0, c11, sum11。最优解b0, c11, sum11。总件数001111。比较总件数a0时总件数11最大所以最优解是(0, 0, 11)。注意虽然a1时bc8比a0时的bc11小但加上a后总件数还是a0大。这再次说明了为什么不能提前break。预期输出0 0 115. 常见错误与调试技巧在实现和调试这道题时以下几个坑点需要特别注意优先级理解错误这是最常见的错误。误以为目标是“先让a最大”而忽略了总件数abc才是第一优先级。必须严格按照总件数 a b的顺序进行比较。枚举不完整在a的循环中如果找到一组解就break可能会错过总件数更大的解当a更小时。务必遍历所有可能的a。内层求解逻辑错误对于固定的a和rest求解b和c时不能简单地让b从大到小或c从大到小枚举然后取第一个解。必须确保找到的解是满足bc最大且在bc最大时b最大的。我们优化后的find_optimal_bc函数正确处理了这一点。无解判断遗漏题目要求如果无法恰好花光n元输出-1。需要初始化一个“无解”状态如best_a -1并在最后根据此状态输出。整数溢出本题n在合理范围内通常n 10^5a, b, c都是非负整数用int足够不会溢出。边界条件测试n0应该输出0 0 0什么都不买恰好花光。n3,4,7应该分别输出0 0 1,0 1 0,1 0 0。n1,2,5应该输出-1。较大的n如100000确保程序能在规定时间通常1秒内运行完毕。调试方法打印中间变量在循环中打印a,rest, 调用find_optimal_bc返回的b, c以及当前总件数对比自己的计算。编写暴力对拍程序对于较小的n比如n100写一个三重循环的暴力枚举程序找出所有可行解并手动按照优先级排序与你的优化程序的结果对比。这是验证算法正确性的黄金标准。单步调试使用IDE如VS Code、Dev C的单步调试功能跟踪变量的变化观察比较逻辑是否按预期执行。6. 总结与举一反三“文具订购”这道题虽然来自入门组但其蕴含的多重条件优化和枚举优化思想非常重要。它教会我们问题转化将生活问题转化为严谨的数学模型方程与约束条件。优先级处理当目标函数有多个且优先级不同时如何设计比较逻辑。这在很多贪心、搜索题中都会出现。枚举优化暴力枚举是起点但必须根据数据范围和问题特性进行优化。本题的优化路径是三重循环 → 两重循环枚举a和b→ 单重循环枚举a内层O(1)求解。核心在于利用数学性质模运算、方程通解减少枚举量。贪心与证明在find_optimal_bc中我们使用了贪心策略让c尽可能多来最大化bc。对于竞赛有时需要直觉性的贪心并验证对于更严谨的情况可能需要简单的证明如通过通解形式分析。这类问题的变种很多比如物品价格变化或者物品种类增多。目标函数变化比如要求a*b*c最大或者要求某种物品不少于多少件。钱不一定非要花光可以剩下一些但要求剩余钱最少。解决它们的关键依然是清晰定义变量和约束确定优化目标与优先级设计高效的枚举或搜索策略并小心处理边界条件。多练习此类题目对培养扎实的编程思维和竞赛手感大有裨益。