🏰《数据结构王国 · 编程题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 × b
（2）⚠️如果作业券不够怎么办？
👉 就把一些“方式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️⃣ 灵活调整资源分配
九、📌记忆口诀
👉 不能直接算答案
👉 就用二分去“猜答案”
