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$。

#include <cstdio>
#include <algorithm>
using namespace std;

int n, m, a, b; // 两种资源的数量：n, m；两种资源的单位消耗：a, b
int l, r;        // 二分查找的左右边界

// 检查是否能够制造v个物品
int check(int v) {
    long long x, y, t; // 使用long long防止溢出
    // 假设全部使用第一种方式制造：每个物品消耗(a, b)
    x = 1ll * v * a; // 对资源n的总消耗
    y = 1ll * v * b; // 对资源m的总消耗

    // 如果资源m的消耗超过上限m
    if (y > m) {
        // 计算需要将多少个物品从方式1切换到方式2
        // 切换1个物品：资源n消耗增加(b-a)，资源m消耗减少(b-a)
        // 需要的最小切换次数t：满足 y - t*(b-a) <= m
        // 向上取整公式：(被除数 + 除数 - 1) / 除数
        t = (y - m + (b - a) - 1) / (b - a);
        
        // 执行切换：调整资源消耗
        y -= t * (b - a); // 资源m消耗减少
        x += t * (b - a); // 资源n消耗增加
    }
    
    // 检查调整后的资源消耗是否满足约束
    // 注意：即使切换次数t过多（超过v），这里仍能正确反映可行性（x过大必然失败）
    return x <= n && y <= m; // 资源n和m均不超过上限
}

int main() {
    // 输入资源总量和单位消耗
    scanf("%d%d", &n, &m);
    scanf("%d%d", &a, &b);
    
    // 标准化：确保 n <= m 且 a <= b（简化问题）
    if (n > m) swap(n, m);
    if (a > b) swap(a, b);
    
    // 特殊情况：当a等于b时
    if (a == b) {
        // 每个物品固定消耗资源(a, a)，限制因素是资源n（因为n<=m）
        printf("%d\n", n / a); // 直接计算最大物品数
        return 0;
    }
    
    // 二分查找最大可行的物品数量v
    l = 0;          // 左边界（最小0个物品）
    r = n;          // 右边界（最大n个物品，因为每个物品至少消耗1单位n）
    while (l < r) {
        // 取中点（向上取整，避免死循环）
        int mid = (l + r + 1) >> 1;
        if (check(mid)) // 如果mid个物品可行
            l = mid;    // 尝试更大的数量
        else
            r = mid - 1; // 否则减少数量
    }
    // 输出结果：r是最大可行物品数
    printf("%d\n", r);
    return 0;
}

问题核心 小A有n张课堂券和m张作业券，兑换规则有两种：

用a张课堂券 + b张作业券换1份奖品

用b张课堂券 + a张作业券换1份奖品

我们需要找出最多能换多少份奖品。

关键思路 统一兑换方式：

首先确保 a >= b（如果不满足就交换两种券和对应数量）

这样第一种方式 (a课堂 + b作业) 消耗课堂券更多

第二种方式 (b课堂 + a作业) 消耗作业券更多

基础检查：

最省课堂券的兑换方式：每次用第二种方式（只消耗 b 张课堂券）

最省作业券的兑换方式：每次用第一种方式（只消耗 a 张作业券）

所以最多能换 min(n/b, m/a) 份

灵活调整：

我们可以先用最省的方式兑换 t 份

然后调整部分兑换方式：

把1次"省课堂券方式"改成"省作业券方式"

需要额外消耗 (a-b) 张课堂券

但能节省 (a-b) 张作业券

检查剩余券是否支持这样的调整

二分搜索：

从0到最大可能份数之间搜索

对每个候选份数 t 检查是否可行

逐步缩小范围找到最大值