[GESP202506 五级] 奖品兑换

题目描述

班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。具体来说，可以使用 $a$ 张课堂优秀券和 $b$ 张作业优秀券兑换一份奖品，或者使用 $b$ 张课堂优秀券和 $a$ 张作业优秀券兑换一份奖品。

现在小 A 有 $n$ 张课堂优秀券和 $m$ 张作业优秀券，他最多能兑换多少份奖品呢？

输入格式

第一行，两个正整数 $n,m$，分别表示小 A 持有的课堂优秀券和作业优秀券的数量。

第二行，两个正整数 $a,b$，表示兑换一份奖品所需的两种券的数量。

输出格式

输出共一行，一个整数，表示最多能兑换的奖品份数。

输入输出样例 #1

输入 #1

8 8
2 1

输出 #1

5

输入输出样例 #2

输入 #2

314159 2653589
27 1828

输出 #2

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$。

提交链接

奖品兑换

思路分析

对于 $60\%$ 的测试点的思路：

🧠 解题思路：暴力枚举。

1. 枚举兑换 (a, b) 型奖品的次数为 $i$；

2. 枚举兑换 (b, a) 型奖品的次数为 $j$；

3. 判断是否能用现有的 $n$ 张课堂券和 $m$ 张作业券完成这 $i+j$ 次兑换；

4. 如果能，则更新当前最大兑换份数 cnt = max(cnt, i + j)；

5. 最终输出最大值 $cnt$。

🔍 枚举逻辑解释

每一次枚举 (i, j)，对应尝试使用 $i$ 次第一种组合和 $j$ 次第二种组合；

• 计算总共需要多少课堂券：i * a + j * b；

• 计算总共需要多少作业券：i * b + j * a；

如果二者都不超过所拥有的 $n$ 和 $m$，就认为当前方案可行

枚举完所有可能的 $i$, $j$ 组合，取最大合法值

⏱ 时间与空间复杂度

时间复杂度：$O(L^2)$，其中 $L$ 是枚举上限（$60\%$ 的数据 $n$、$m$ 最大为 $500$），满足时间复杂度的要求。

参考代码

#include <bits/stdc++.h>
using namespace std;int main()
{int n, m, a, b;cin >> n >> m; // 小 A 持有的课堂优秀券和作业优秀券的数量。cin >> a >> b; // 兑换一份奖品所需的两种券的数量int cnt = 0;for (int i = 0; i <= 500; i++) // 枚举(a,b)兑换的次数{for (int j = 0; j <= 500; j++) // 枚举(b,a)兑换的次数{int n1 = i * a + j * b, m1 = i * b + j * a;if (n1 <= n && m1 <= m){cnt = max(cnt, i + j);}}}cout << cnt;return 0;
}

对于 $100\%$ 的测试点的思路：

🧠 解题思路

本题本质是一个混合资源分配最大化问题，目标是确定最大可兑换份数 $x$，在满足：

1. 消耗的课堂券总数 $\le n$

2. 消耗的作业券总数 $\le m$

但由于每份奖品可用两种不同方式兑换，直接贪心或模拟不易确定是否可行。因此我们使用：

✅ 二分答案 + 可行性判定

1. 步骤一：二分最大可兑换份数 $x$

   • 初始范围为 [0, 1e9]

   • 每次尝试中间值 $mid$，判断是否存在一种组合方式能兑换 $mid$ 份奖品

2. 步骤二：判定某个兑换数量 $x$ 是否可行（check 函数）

   • 假设使用 $i$ 份方案 $1$（类型 (a,b)）

   • 则剩下的 $x-i$ 份使用方案 $2$（类型 (b,a)）

   总消耗：

   • 课堂券 = i * a + (x - i) * b

   • 作业券 = i * b + (x - i) * a

   • 枚举 $i$ 的可能值（$0$ 到 $x$），判断是否存在满足券数限制的某个 $i$

   • 由于 $x$ 很大，枚举 $i$ 可能较慢，所以我们在 check 函数中也使用二分枚举 $i$。

if(n < m) swap(n , m);
if(a < b) swap(a , b);

• 把较大的券数放在 $n$，较大的需求放在 $a$；
• 多的换多的，少的换少的，符合逻辑。

long long l = 0, r = 1e9, mid, ans;
while (l <= r)
{mid = l + (r - l) / 2;if (check(mid)){ans = mid;l = mid + 1;}else{r = mid - 1;}
}
cout << ans;

• 对奖品总数进行二分
• 奖品越多，需要的券越多，满足单调性

bool check(int x)
{// 总的奖品数量为x 如何分成 (a , b) + (b , a)long long left = 0, right = x, Mid; // 二分(a , b)的数量while (left <= right){Mid = left + (right - left) / 2;long long n1 = Mid * a + (x - Mid) * b, m1 = Mid * b + (x - Mid) * a;if (n1 <= n && m1 <= m){return true;}else if (n1 > n){right = Mid - 1;}else{left = Mid + 1;}}return false;
}

• 总的奖品数量为 $x$，二分 (a,b) 组合的使用数量。
• 对应的课堂券和作业券这两项都不超过 $n$ 和 $m$
• 若课堂券超过 $n$，修改 right = Mid - 1，若作业券超过 $m$，修改 left = Mid + 1
• 使用更多的 (a,b) 组合，对 (n,m) 消耗更多，满足单调性。

参考代码

#include <bits/stdc++.h>
using namespace std;long long n, m, a, b;
bool check(int x)
{//总的奖品数量为x 如何分成 (a , b) + (b , a)long long left = 0 , right = x , Mid;   //二分(a , b)的数量while(left <= right){Mid = left + (right - left) / 2;long long n1 = Mid * a + (x - Mid) * b , m1 = Mid * b + (x - Mid) * a;if(n1 <= n && m1 <= m){return true;}else if(n1 > n){right = Mid - 1;}else{left = Mid + 1;}}return false;}
int main()
{cin >> n >> m; // 小 A 持有的课堂优秀券和作业优秀券的数量。cin >> a >> b; // 兑换一份奖品需要a张课堂优秀券 + b张作业优秀券  或者 b张课堂优秀券 + a张作业优秀券//多的兑换多的 少的兑换少的if(n < m) swap(n , m);if(a < b) swap(a , b);// 枚举枚举总的奖品数量long long l = 0, r = 1e9, mid , ans;while (l <= r){mid = l + (r - l) / 2;if(check(mid)){ans = mid;l = mid + 1;}else{r = mid - 1;}}cout << ans;return 0;
}