【GESP】C++五级真题（二分答案考点） luogu-P13013 [GESP202506 五级] 奖品兑换
GESP C++ 2025年6月五级真题，二分答案考点，题目难度⭐⭐⭐☆☆，五级来说难度适中。洛谷难度等级普及/提高−
luogu-P13013 [GESP202506 五级] 奖品兑换
题目要求
题目背景
为了保证只有时间复杂度正确的代码能够通过本题，时限下降为 400 毫秒。
题目描述
班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。具体来说，可以使用 $a$ 张课堂优秀券和 $b$ 张作业优秀券兑换一份奖品，或者使用 $b$ 张课堂优秀券和 $a$ 张作业优秀券兑换一份奖品。
现在小 A 有 $n$ 张课堂优秀券和 $m$ 张作业优秀券，他最多能兑换多少份奖品呢？
输入格式
第一行，两个正整数 $n,m$，分别表示小 A 持有的课堂优秀券和作业优秀券的数量。
第二行，两个正整数 $a,b$，表示兑换一份奖品所需的两种券的数量。
输出格式
输出共一行，一个整数，表示最多能兑换的奖品份数。
输入输出样例 #1
输入 #1
1
2
8 8
2 1
输出 #1
1
5
输入输出样例 #2
输入 #2
1
2
314159 2653589
27 1828
输出 #2
1
1599
说明/提示
对于 $60\%$ 的测试点，保证 $1 \le a,b \le 100$，$1 \le n,m \le 500$。
对于所有测试点，保证 $1 \le a,b \le 10^4$，$1 \le n,m \le 10^9$。
题目分析
这道题是一个最大化问题，可以通过二分答案来解决。
核心思想
我们需要求出最多能兑换多少份奖品，设这个数量为 $k$。 显然，如果能兑换 $k$ 份奖品，那么一定也能兑换 $k-1$ 份。这种单调性允许我们使用二分查找来确定最大的 $k$。
判定条件：
对于给定的总奖品数 $k$，假设我们兑换了 $x$ 份第一种方案（$a$ 张课堂券 + $b$ 张作业券），那么剩下的 $k-x$ 份必须是第二种方案（$b$ 张课堂券 + $a$ 张作业券）。
我们需要检查是否存在一个整数 $x$ ($0 \le x \le k$)，使得课堂券和作业券的总消耗都不超过拥有的数量 $n$ 和 $m$。这可以通过解两个关于 $x$ 的不等式来完成： \(a \cdot x + b \cdot (k - x) \le n\) \(b \cdot x + a \cdot (k - x) \le m\) 通过数学推导，我们可以求出 $x$ 的合法取值范围 $[L, R]$。只要这个范围不为空且与 $[0, k]$ 有交集，那么 $k$ 就是可行的。具体推导如下：
首先，我们有以下两个关于 $x$ 的不等式：
- 课堂券消耗：$a \cdot x + b \cdot (k - x) \le n$
- 作业券消耗：$b \cdot x + a \cdot (k - x) \le m$
展开并整理这两个不等式：
对于课堂券消耗：
\(a \cdot x + b \cdot (k - x) \le n\) \((a - b)x \le n - bk \quad \text{......(式1)}\)
对于作业券消耗：
\(-(a - b)x \le m - ak\) \((a - b)x \ge ak - m \quad \text{......(式2)}\)
结合 (式1) 和 (式2)，我们得到关于 $(a-b)x$ 的范围：
\[ak - m \le (a - b)x \le n - bk\]接下来，我们需要根据 $a$ 和 $b$ 的大小关系来解出 $x$ 的范围。
情况一：$a > b$
此时 $a - b$ 为正数，可以直接除以 $(a - b)$，不等号方向不变：
\[\frac{ak - m}{a - b} \le x \le \frac{n - bk}{a - b}\]由于 $x$ 必须是整数，所以 $x$ 的数学合法取值范围 $[L_{calc}, R_{calc}]$ 为：
\(L_{calc} = \lceil \frac{ak - m}{a - b} \rceil\) \(R_{calc} = \lfloor \frac{n - bk}{a - b} \rfloor\)
情况二：$a < b$
此时 $a - b$ 为负数。此时 $b - a$ 为正数，可以直接除以 $(b - a)$：
\[\frac{bk - n}{b - a} \le x \le \frac{m - ak}{b - a}\]由于 $x$ 必须是整数，所以 $x$ 的数学合法取值范围 $[L_{calc}, R_{calc}]$ 为：
\(L_{calc} = \lceil \frac{bk - n}{b - a} \rceil\) \(R_{calc} = \lfloor \frac{m - ak}{b - a} \rfloor\)
情况三：$a = b$
此时 $a - b = 0$。不等式链变为：
\[ak - m \le 0 \cdot x \le n - bk\]这意味着必须满足：
\(ak - m \le 0 \implies ak \le m\) \(0 \le n - bk \implies bk \le n\)
如果这两个条件都满足，那么任意 $x \in [0, k]$ 都是合法的。此时 $L_{calc}=0, R_{calc}=k$。如果任一条件不满足，则不存在合法的 $x$。
最终判定条件：
在得到 $x$ 的数学合法取值范围 $[L_{calc}, R_{calc}]$ 后，还需要考虑 $x$ 必须满足 $0 \le x \le k$ 的条件。 因此，最终有效的 $x$ 的范围是 $[L_{final}, R_{final}]$，其中： \(L_{final} = \max(0, L_{calc})\) \(R_{final} = \min(k, R_{calc})\) 如果 $L_{final} \le R_{final}$，则表示存在至少一个整数 $x$ 满足所有条件，即当前的 $k$ 是可行的。
核心代码逻辑
- 输入处理与预处理：首先读取输入的 $n, m, a, b$。为了简化后续的分类讨论，在主函数中预先判断并交换 $a, b$，确保满足 $a \le b$。
- 二分查找框架：使用
left = 0,right为可能的理论最大值（如 $(n+m)/(a+b)$ 或 $2 \times 10^9$）进行二分查找。每次取中点mid作为尝试的总奖品数，调用check(mid)函数进行判定。如果可行，尝试更大的答案（left = mid + 1）；否则减小范围（right = mid - 1）。 - Check 函数判定：
check(k)函数用于判断是否能兑换 $k$ 份奖品。- 若 $a = b$，直接检查总需求是否超过资源限制（即 $a \times k \le n$ 且 $a \times k \le m$）。
- 若 $a < b$（已通过预处理保证），根据不等式推导出方案一兑换数量 $x$ 的合法范围 $[L, R]$：
- 下界 $L$ 由课堂券限制得出：$x \ge \lceil \frac{b \cdot k - n}{b - a} \rceil$，且需注意 $x \ge 0$。
- 上界 $R$ 由作业券限制得出：$x \le \lfloor \frac{m - a \cdot k}{b - a} \rfloor$，且需注意 $x \le k$。
- 最后判断是否存在合法的整数 $x$，即判断 $L \le R$。
本题的核心代码逻辑主要集中在 check(k) 函数中，该函数用于判断在给定总奖品数 $k$ 的情况下，是否有可能通过调整两种兑换方案的次数 $x$ 和 $y$ (其中 $x+y=k$) 来满足课堂券和作业券的拥有量限制。具体的数学推导和分类讨论（针对 $a > b$, $a < b$, $a = b$ 三种情况）在“题目分析”的“判定条件”部分已详细说明。
main 函数则实现了二分查找的框架，通过不断调用 check(k) 函数来收敛答案，最终找到能够兑换的最大奖品份数。为了简化 check 函数内部的逻辑，在 main 函数中预先保证了 $a \le b$。
复杂度
时间复杂度：二分查找的范围大约是 $0$ 到 $2 \times 10^9$，需要循环约 31 次。每次判定计算量为 $O(1)$。 总时间复杂度为 $O(\log(n+m))$，远小于 400ms 的时限。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cmath>
#include <iostream>
typedef long long ll;
ll n, m, a, b;
// 检查是否能兑换 k 份奖品
// 假设使用了 x 张第一种方案（a 张课堂券，b 张作业券）
// 那么使用了 k - x 张第二种方案（b 张课堂券，a 张作业券）
// 需满足：
// x * a + (k - x) * b <= n
// x * b + (k - x) * a <= m
// 因为在 main 函数中保证了 a >= b，所以 a - b >= 0
bool check(ll k) {
ll diff = a - b;
ll l = 0;
// 计算 x 的下界：x >= (k * a - m) / (a - b)
if (a * k > m) {
l = std::ceil((a * k - m) / (double)diff);
}
// 如果即使全部用第二种方案（消耗 b 张课堂券），课堂券也不够，直接返回 false
if (b * k > n) {
return false;
}
// 计算 x 的上界：x <= (n - k * b) / (a - b)
ll r = (n - b * k) / diff;
// x 不能超过总奖品数 k
r = std::min(r, k);
// 如果存在合法的 x (即区间 [l, r] 非空)，则说明可以兑换 k 份
return l <= r;
}
int main() {
std::cin >> n >> m >> a >> b;
ll count = 0;
// 特殊情况：如果两种方案消耗相同，直接看总资源能换多少
// 实际上此时 a=b，只能换 min(n, m) / a 份
if (a == b) {
count = std::min(n, m) / a;
std::cout << count;
return 0;
}
// 保证 a >= b，方便 check 函数中的不等式处理（避免除以负数）
if (a < b) {
std::swap(a, b);
}
// 二分答案
// 答案的范围在 0 到 max(n, m) 之间
ll left = 0;
ll right = std::max(n, m);
ll ans = 0;
while (left <= right) {
ll mid = left + (right - left) / 2;
if (check(mid)) {
ans = mid; // 如果能换 mid 份，尝试更多
left = mid + 1;
} else {
right = mid - 1; // 否则减少尝试数量
}
}
std::cout << ans;
return 0;
}
另附一种贪心的解法，不过在洛谷400ms的要求下，会超时，但是思路是没问题的，这其实是我最开始想到的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cmath>
// 贪心解法
int main() {
// 定义变量 n, m 分别表示小 A 持有的课堂优秀券和作业优秀券的数量
// a, b 表示兑换一份奖品所需的两种券的数量
int n, m, a, b;
std::cin >> n >> m >> a >> b;
// 为了方便贪心策略，将拥有的券数和兑换所需的券数都按大小排序
// l1 为较多的券数，s1 为较少的券数
int l1 = std::max(n, m);
int s1 = std::min(n, m);
// l2 为较大的兑换需求，s2 为较小的兑换需求
int l2 = std::max(a, b);
int s2 = std::min(a, b);
int count = 0; // 记录能兑换的奖品数量
// 尝试进行循环兑换
while (l1 >= 0 && s1 >= 0) {
// 贪心策略：尝试用较多的券去填补较大的需求
// 如果当前的券足够进行一次兑换（大对大，小对小）
if (l1 >= l2 && s1 >= s2) {
count++; // 奖品数加一
l1 -= l2; // 扣除相应的券
s1 -= s2;
} else {
// 如果不够兑换，则退出循环
break;
}
// 每次兑换后，剩余的券数量可能会发生变化，导致 l1 不再是较大的那个
// 所以需要重新检查并交换，确保 l1 始终大于等于 s1
if (l1 < s1) {
int tmp = l1;
l1 = s1;
s1 = tmp;
}
}
// 输出最终兑换的奖品总数
std::cout << count << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
