洛谷P13013题解

分析

这道题目要求我们计算在给定两种优秀券的数量限制下，最多可以兑换多少份奖品。兑换规则有两种方式：

1. 使用 $a$ 张课堂券和 $b$ 张作业券。

2. 使用 $b$ 张课堂券和 $a$ 张作业券。

首先我们确保 $a \le b$，处理会更加方便，也就是说当 $a > b$ 时需要交换 $a$ 和 $b$。

当 $a = b$ 时，兑换方式只有一种，直接取两种券数量的较小值除以 $a$ 即可。

对于 $a \neq b$ 情况，我们使用二分查找来确定最大兑换份数 $\operatorname{mid}$。

对于 $\operatorname{mid}$，我们需要满足：

1. 每种券至少能提供 $a \times \operatorname{mid}$ 张。

2. 剩余券的数量能够满足另一种兑换方式的需求。

所以得出条件：

$$\operatorname{mid} \le (n - a \times \operatorname{mid}) / (b - a) + (m - a \times \operatorname{mid}) / (b - a)$$

代码

#include<bits/stdc++.h>
using namespace std;
int main() {
	long long n, m, a, b; //一定要开 long long
	cin >> n >> m >> a >> b;
	if (a > b) swap(a, b); 
	if (a == b) {
		cout << min(n, m) / a;
		return 0;
	}
	long long l = 0, r = 1e9;
	while (l < r) {
		long long mid = (l + r + 1) / 2;
		if (n < a * mid || m < a * mid || (n - a * mid) / (b - a) + (m - a * mid) / (b - a) < mid) r = mid - 1;
		else l = mid;
	}
	cout << l;
	return 0;
}