《数据结构王国 · 编程题1奖品兑换大作战》》一、故事背景在班级王国里 老师发了两种奖励券 课堂优秀券蓝色 作业优秀券绿色小 A 拿着一堆券想去换奖品 二、兑换规则有两种兑换方式方式1 用a张课堂券 b张作业券 → 换 1 个奖品方式2 用b张课堂券 a张作业券 → 换 1 个奖品三、❓问题 小 A 有n 张课堂券m 张作业券最多可以换多少个奖品四、关键思考1、核心问题 每换一次就会消耗券 两种方式可以混着用2、❗关键难点 怎么搭配才能换最多五、结题思路我们来想一个策略1、思路尝试“换 x 个”行不行 假设我们总共换x个奖品那我们要检查这些券够不够用2、检查方法假设有一部分用方式1有一部分用方式2但我们不用真的分 用一个“调整技巧”判断就行这就是参考程序的核心思想3、核心技巧1 如果我们想换 x 个奖品先假设全部用方式1 消耗课堂x × a作业x × b2⚠️如果作业券不够怎么办 就把一些“方式1”改成“方式2” 因为方式2会少用一些作业券多用一些课堂券(3) 最终目标 调整后满足课堂 ≤ n作业 ≤ m六、完整解法二分答案 问题变成最多能换多少次1、做法 用二分查找答案2、步骤① 左边0② 右边最多可能比如 n ③ 每次猜一个 mid尝试换 mid 次④ 用 check(mid) 判断是否可行完整参考代码#include iostream using namespace std; long long n, m, a, b; // 检查能不能换 v 个奖品 bool check(long long v) { long long x v * a; // 课堂券 long long y v * b; // 作业券 // 如果作业券不够就调整 if (y m) { long long t (y - m (b - a) - 1) / (b - a); y - t * (b - a); x t * (b - a); } return x n y m; } int main() { cin n m; cin a b; if (n m) swap(n, m); if (a b) swap(a, b); long long l 0, r n; while (l r) { long long mid (l r 1) / 2; if (check(mid)) l mid; else r mid - 1; } cout l endl; return 0; }七、举例方便理解1、输入n 8, m 8 a 2, b 12、解释 一次兑换用 2 课堂 1 作业或用 1 课堂 2 作业3、尝试 最多能换多少 答案5八、最终总结这题用到的知识点1️⃣ 复杂问题 → 转成“能不能做到”2️⃣ 用函数 check 判断3️⃣ 用二分找最大答案4️⃣ 灵活调整资源分配九、记忆口诀 不能直接算答案 就用二分去“猜答案”