202506-奖品兑换(luogu-P13013)

GESP C++ 2025年6月五级真题，二分答案考点，题目难度⭐⭐⭐☆☆，五级来说难度适中。洛谷难度等级普及/提高−

luogu-P13013 [GESP202506 五级] 奖品兑换

题目要求

题目背景

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

题目描述

班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。具体来说，可以使用 $a$ 张课堂优秀券和 $b$ 张作业优秀券兑换一份奖品，或者使用 $b$ 张课堂优秀券和 $a$ 张作业优秀券兑换一份奖品。
现在小 A 有 $n$ 张课堂优秀券和 $m$ 张作业优秀券，他最多能兑换多少份奖品呢？

输入格式

第一行，两个正整数 $n,m$ ，分别表示小 A 持有的课堂优秀券和作业优秀券的数量。
第二行，两个正整数 $a,b$ ，表示兑换一份奖品所需的两种券的数量。

输出格式

输出共一行，一个整数，表示最多能兑换的奖品份数。

输入输出样例 #1

输入 #1

8 8
2 1

输出 #1

输入输出样例 #2

输入 #2

314159 2653589
27 1828

输出 #2

说明/提示

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

题目分析

这道题是一个最大化问题，可以通过二分答案来解决。

核心思想

我们需要求出最多能兑换多少份奖品，设这个数量为 $k$ 。显然，如果能兑换 $k$ 份奖品，那么一定也能兑换 $k-1$ 份。这种单调性允许我们使用二分查找来确定最大的 $k$ 。

判定条件：

对于给定的总奖品数 $k$ ，假设我们兑换了 $x$ 份第一种方案（ $a$ 张课堂券 + $b$ 张作业券），那么剩下的 $k-x$ 份必须是第二种方案（ $b$ 张课堂券 + $a$ 张作业券）。

我们需要检查是否存在一个整数 $x$ ( $0 \le x \le k$ )，使得课堂券和作业券的总消耗都不超过拥有的数量 $n$ 和 $m$ 。这可以通过解两个关于 $x$ 的不等式来完成：

a \cdot x + b \cdot (k - x) \le n

b \cdot x + a \cdot (k - x) \le m

通过数学推导，我们可以求出 $x$ 的合法取值范围 $[L, R]$ 。只要这个范围不为空且与 $[0, k]$ 有交集，那么 $k$ 就是可行的。具体推导如下：

首先，我们有以下两个关于 $x$ 的不等式：

课堂券消耗： $a \cdot x + b \cdot (k - x) \le n$
作业券消耗： $b \cdot x + a \cdot (k - x) \le m$

展开并整理这两个不等式：

对于课堂券消耗：

a \cdot x + b \cdot (k - x) \le n

(a - b)x \le n - bk \quad \text{......(式1)}

对于作业券消耗：

-(a - b)x \le m - ak

(a - b)x \ge ak - m \quad \text{......(式2)}

结合 (式1) 和 (式2)，我们得到关于 $(a-b)x$ 的范围：

ak - m \le (a - b)x \le n - bk

接下来，我们需要根据 $a$ 和 $b$ 的大小关系来解出 $x$ 的范围。

情况一： $a > b$

此时 $a - b$ 为正数，可以直接除以 $(a - b)$ ，不等号方向不变：

\frac{ak - m}{a - b} \le x \le \frac{n - bk}{a - b}

由于 $x$ 必须是整数，所以 $x$ 的数学合法取值范围 $[L_{calc}, R_{calc}]$ 为：

L_{calc} = \lceil \frac{ak - m}{a - b} \rceil

R_{calc} = \lfloor \frac{n - bk}{a - b} \rfloor

情况二： $a < b$

此时 $a - b$ 为负数。此时 $b - a$ 为正数，可以直接除以 $(b - a)$ ：

\frac{bk - n}{b - a} \le x \le \frac{m - ak}{b - a}

由于 $x$ 必须是整数，所以 $x$ 的数学合法取值范围 $[L_{calc}, R_{calc}]$ 为：

L_{calc} = \lceil \frac{bk - n}{b - a} \rceil

R_{calc} = \lfloor \frac{m - ak}{b - a} \rfloor

情况三： $a = b$

此时 $a - b = 0$ 。不等式链变为：

ak - m \le 0 \cdot x \le n - bk

这意味着必须满足：

ak - m \le 0 \implies ak \le m

0 \le n - bk \implies bk \le n

如果这两个条件都满足，那么任意 $x \in [0, k]$ 都是合法的。此时 $L_{calc}=0, R_{calc}=k$ 。如果任一条件不满足，则不存在合法的 $x$ 。

最终判定条件：

在得到 $x$ 的数学合法取值范围 $[L_{calc}, R_{calc}]$ 后，还需要考虑 $x$ 必须满足 $0 \le x \le k$ 的条件。因此，最终有效的 $x$ 的范围是 $[L_{final}, R_{final}]$ ，其中：

L_{final} = \max(0, L_{calc})

R_{final} = \min(k, R_{calc})

如果 $L_{final} \le R_{final}$ ，则表示存在至少一个整数 $x$ 满足所有条件，即当前的 $k$ 是可行的。

核心代码逻辑

输入处理与预处理：首先读取输入的 $n, m, a, b$ 。为了简化后续的分类讨论，在主函数中预先判断并交换 $a, b$ ，确保满足 $a \le b$ 。
二分查找框架：使用 left = 0, right 为可能的理论最大值（如 $(n+m)/(a+b)$ 或 $2 \times 10^9$ ）进行二分查找。每次取中点 mid 作为尝试的总奖品数，调用 check(mid) 函数进行判定。如果可行，尝试更大的答案（left = mid + 1）；否则减小范围（right = mid - 1）。
Check 函数判定：check(k) 函数用于判断是否能兑换 $k$ $k$ 份奖品。
- 若 $a = b$ ，直接检查总需求是否超过资源限制（即 $a \times k \le n$ 且 $a \times k \le m$ ）。
- 若 $a < b$ （已通过预处理保证），根据不等式推导出方案一兑换数量 $x$ 的合法范围 $[L, R]$ ：
- 下界 $L$ 由课堂券限制得出： $x \ge \lceil \frac{b \cdot k - n}{b - a} \rceil$ ，且需注意 $x \ge 0$ 。
- 上界 $R$ 由作业券限制得出： $x \le \lfloor \frac{m - a \cdot k}{b - a} \rfloor$ ，且需注意 $x \le k$ 。
- 最后判断是否存在合法的整数 $x$ ，即判断 $L \le R$ 。

本题的核心代码逻辑主要集中在 check(k) 函数中，该函数用于判断在给定总奖品数 $k$ 的情况下，是否有可能通过调整两种兑换方案的次数 $x$ 和 $y$ (其中 $x+y=k$ ) 来满足课堂券和作业券的拥有量限制。具体的数学推导和分类讨论（针对 $a > b$ , $a < b$ , $a = b$ 三种情况）在“题目分析”的“判定条件”部分已详细说明。

main 函数则实现了二分查找的框架，通过不断调用 check(k) 函数来收敛答案，最终找到能够兑换的最大奖品份数。为了简化 check 函数内部的逻辑，在 main 函数中预先保证了 $a \le b$ 。

复杂度

时间复杂度：二分查找的范围大约是 $0$ 到 $2 \times 10^9$ ，需要循环约 31 次。每次判定计算量为 $O(1)$ 。总时间复杂度为 $O(\log(n+m))$ ，远小于 400ms 的时限。

示例代码

#include <cmath>
#include <iostream>

typedef long long ll;

ll n, m, a, b;

// 检查是否能兑换 k 份奖品
// 假设使用了 x 张第一种方案（a 张课堂券，b 张作业券）
// 那么使用了 k - x 张第二种方案（b 张课堂券，a 张作业券）
// 需满足：
// x * a + (k - x) * b <= n
// x * b + (k - x) * a <= m
// 因为在 main 函数中保证了 a >= b，所以 a - b >= 0
bool check(ll k) {
    ll diff = a - b;
    ll l = 0;
    // 计算 x 的下界：x >= (k * a - m) / (a - b)
    if (a * k > m) {
        l = std::ceil((a * k - m) / (double)diff);
    }
    // 如果即使全部用第二种方案（消耗 b 张课堂券），课堂券也不够，直接返回 false
    if (b * k > n) {
        return false;
    }
    // 计算 x 的上界：x <= (n - k * b) / (a - b)
    ll r = (n - b * k) / diff;
    // x 不能超过总奖品数 k
    r = std::min(r, k);

    // 如果存在合法的 x (即区间 [l, r] 非空)，则说明可以兑换 k 份
    return l <= r;
}

int main() {
    std::cin >> n >> m >> a >> b;

    ll count = 0;

    // 特殊情况：如果两种方案消耗相同，直接看总资源能换多少
    // 实际上此时 a=b，只能换 min(n, m) / a 份
    if (a == b) {
        count = std::min(n, m) / a;
        std::cout << count;
        return 0;
    }

    // 保证 a >= b，方便 check 函数中的不等式处理（避免除以负数）
    if (a < b) {
        std::swap(a, b);
    }

    // 二分答案
    // 答案的范围在 0 到 max(n, m) 之间
    ll left = 0;
    ll right = std::max(n, m);
    ll ans = 0;
    while (left <= right) {
        ll mid = left + (right - left) / 2;
        if (check(mid)) {
            ans = mid;  // 如果能换 mid 份，尝试更多
            left = mid + 1;
        } else {
            right = mid - 1;  // 否则减少尝试数量
        }
    }

    std::cout << ans;

    return 0;
}

另附一种贪心的解法，不过在洛谷400ms的要求下，会超时，但是思路是没问题的，这其实是我最开始想到的方法。

#include <iostream>
#include <cmath>

// 贪心解法
int main() {
    // 定义变量 n, m 分别表示小 A 持有的课堂优秀券和作业优秀券的数量
    // a, b 表示兑换一份奖品所需的两种券的数量
    int n, m, a, b;
    std::cin >> n >> m >> a >> b;

    // 为了方便贪心策略，将拥有的券数和兑换所需的券数都按大小排序
    // l1 为较多的券数，s1 为较少的券数
    int l1 = std::max(n, m);
    int s1 = std::min(n, m);
    // l2 为较大的兑换需求，s2 为较小的兑换需求
    int l2 = std::max(a, b);
    int s2 = std::min(a, b);

    int count = 0;  // 记录能兑换的奖品数量
    // 尝试进行循环兑换
    while (l1 >= 0 && s1 >= 0) {
        // 贪心策略：尝试用较多的券去填补较大的需求
        // 如果当前的券足够进行一次兑换（大对大，小对小）
        if (l1 >= l2 && s1 >= s2) {
            count++;   // 奖品数加一
            l1 -= l2;  // 扣除相应的券
            s1 -= s2;
        } else {
            // 如果不够兑换，则退出循环
            break;
        }
        // 每次兑换后，剩余的券数量可能会发生变化，导致 l1 不再是较大的那个
        // 所以需要重新检查并交换，确保 l1 始终大于等于 s1
        if (l1 < s1) {
            int tmp = l1;
            l1 = s1;
            s1 = tmp;
        }
    }
    // 输出最终兑换的奖品总数
    std::cout << count << std::endl;
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2025年11月26日

202503-原根判断(luogu-P11961)202506-最大公因数(luogu-P13014)