P13013 [GESP202506 五级] 奖品兑换

题目背景

为了保证只有时间复杂度正确的代码能够通过本题，时限下降为 400 毫秒。

题目描述

班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。具体来说，可以使用 $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$。

一件喜事

本OIder在GESP考试的时候成功AK这道题！

你们最爱的的代码时间

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

如果喜欢博主，别忘关注加点赞！