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

HSTYYH · 2025-07-02 18:35:46 · 题解

非常不错的一道二分答案题目，整体不算太难。

思路如下：我们需要确定最多能兑换多少份奖品。兑换一份奖品可以使用两种方式：一种是使用 a 张课堂优秀券和 b 张作业优秀券，另一种是使用 b 张课堂优秀券和 a 张作业优秀券。

给出 n 张课堂优秀券和 m 张作业优秀券，我们需要找出最大的兑换份数 mid ，使得存在非负整数 x 和 y ，其中 x+y=mid ，需要满足以下条件：

• a\times x + b \times y \le n
• b\times x + a \times y \le m

使用二分法来寻找最大的 mid 。二分范围的下界为 0 ，上界为 \max(n,m) / \min(a,b) + 1 （ 确保覆盖可能的解）。同时，检查函数中对于每个候选的 t ，检查是否存在非负整数 x（0 \le x \le t） 满足：

• (a - b)\times x \le n - b\times t
• (a - b) \times x \ge a \times t - m

根据 a 和 b 的大小关系，分情况处理：

• 当 a 和 b 相等时，只需验证 a\times t \le n 且 a\times t ≤ m 。
• 当 a > b 时，计算 x 的下界和上界，并检查是否存在整数 x 在 [0, t] 范围内。
• 当 a < b 时，同样计算 x 的下界和上界，并检查是否存在整数 x 在 [0, t] 范围内。

剩下就是二分答案的模板了，相信大家都可以看懂，上代码：

#include <bits/stdc++.h>
using namespace std;

long long n, m, a, b;

bool check(long long t){

    if((a + b) * t > n + m) 
        return false;

    if(a == b){
        if( a * t <= n &&  a * t <= m)
            return true;
        else
            return false;
    }

    double low, high;
    if(a > b){
        low = (1.0 * a * t - m) / (a - b);
        high = (1.0 * n - b * t) / (a - b);
    }
    else{
        low = (1.0 * n - b * t) /(a - b);
        high = (1.0 * a * t - m) /(a - b);
    }

    long long L = ceil(low);
    long long R = floor(high);

    L = max(L, (long long)0);
    R = min(R, t);

    return(L <= R);
}

int main(){

    cin >> n >> m;
    cin >> a >> b;

    long long ans = 0;
    long long left = 0;
    long long right = max(n,m)/min(a,b) + 1;

    while(left <= right){
        long long mid =(left + right) / 2;
        if(check(mid)){
            ans = mid;
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }

    cout << ans;

    return 0;
}