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

· · 题解

题目传送门

故事

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

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

题意

小 A 有 n 张课堂优秀券，m 张作业优秀券。

小 A 可以花 a 张课堂优秀券和 b 张作业优秀券或者 b 张课堂优秀券和 a 张作业优秀券来换取一个奖品。

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

分析

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

先要确保 n \ge m, a \ge b，然后是基本二分结构，结构还是讲一下吧：

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

输入加二分框架：

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 CODE

#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;
}