当前位置：首页 > news >正文

GESP2025年6月认证C++五级( 第三部分编程题（1、奖品兑换））

news 2026/4/30 8:30:47

🏰《数据结构王国 · 编程题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; }