题解：P13013 [GESP202506 五级] 奖品兑换

题目传送门

故事

先吐槽一句，在考试的时候，编译器给我卡爆了，花了半小时才做完了，当时满分了。

然后我信心满满的提交了题解，第二天题解通道给我关了，我愣住了，然后下午发现原来数据加强了，还升黄了，给我打回来了，我只能重构新算法。

题意

小 A 有

n

张课堂优秀券，

m

张作业优秀券。

小 A 可以花

a

张课堂优秀券和

b

张作业优秀券或者

b

张课堂优秀券和

a

张作业优秀券来换取一个奖品。

我们需要求出最多可以换取多少个奖品。

分析

~~考试时就一眼杀了，这题考贪心~~。数据加强后现在题目要用二分了。暴力解法我就不讲了，只能拿部分分，就讲一下能满分的二分算法。

先要确保

n \ge m, a \ge b

，然后是基本二分结构，结构还是讲一下吧：

二分会有起始的 $left$ 和 $right$ 。
循环一般用 while，条件一般为 while(left <= right)。
在循环内部要用 $middle$ 来求 $left$ 和 $right$ 的中间值，即 middle = (left + right) / 2。
以上代码可优化成 middle = left = (right - left) / 2，这样可以确保不会溢出。
通过一个函数的返回值，去修改 $left$ 或 $right$ 的值，即 left = middle + 1 或 right = middle - 1。
二分因为每次减少一半的范围，所以时间复杂度为 $O(\log n)$ 。

输入加二分框架：

CPP

int n, m, a, b, v;
cin >> n >> m >> a >> b;
if (n < m) {
	swap(n, m);
}
if (a < b) { 
	swap(a, b);
}
v = a - b;
int left = 0, right = n;
int ans = 0;
while (left <= right) {
	int middle = left + (right - left) / 2;
  if (check(middle) == 1) {
		ans = max(ans, middle);
		left = middle + 1;
	} else {
		right = middle - 1;
	}
}

接下来就是写

\operatorname{check}

函数了。

把

middle

作为参数传入，求出按当前比例分配的两个量

x,y

，如果

x

超出上限

n

时，需要转换

x

和

y

，而转换量为

(x - n + v - 1) \div v

，最后判断以下

x,y

与

n,m

之间的关系，返回 0 或 1，在二分循环中做出相应修改，结束后输出答案即可。

注意

此题因

a,b

较大，需要使用 #define int long long。

AC CDOE

CPP

#include <bits/stdc++.h>
#define int long long //不开80分
using namespace std;
int n, m, a, b, v;
bool check(int middle) { //求解
	int x = a * middle, y = b * middle; //按当前比例分配的总量
	if (x > n) { //若x超过上限n时
		int k = (x - n + v - 1) / v; //需要转换的量
		x -= k * v, y += k * v; //等比例转换
	}
	if (x <= n && y <= m) { //最后判断
		return 1;
	}
	return 0;
}
signed main() {
	cin >> n >> m >> a >> b;
	if (n < m) { //保证n>=m
		swap(n, m);
	}
	if (a < b) { //保证a>=b
		swap(a, b);
	}
	v = a - b; //修改
	int left = 0, right = n; //二分l,r
	int ans = 0;
	while (left <= right) { //二分条件
		int middle = left + (right - left) / 2; //二分mid
		if (check(middle) == 1) { //两种情况
			ans = max(ans, middle); //修改
			left = middle + 1; //缩减范围
		} else {
			right = middle - 1; //缩减范围
		}
	}
	cout << ans; //输出代码
	return 0;
}

题解：P13013 [GESP202506 五级] 奖品兑换

文章操作

题目传送门

故事

题意

分析

注意

AC CDOE

相关推荐

评论

题解：P13013 [GESP202506 五级] 奖品兑换