OneCoder Avatar
OneCodercoderli.com · 1025 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++五级真题(二分答案考点) luogu-P13013 [GESP202506 五级] 奖品兑换

📅 2025-11-23·✍️ OneCoder·计算中...·⏱️ 15 分钟

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

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

题目要求

题目背景

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

题目描述

班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。具体来说,可以使用 张课堂优秀券和 张作业优秀券兑换一份奖品,或者使用 张课堂优秀券和 张作业优秀券兑换一份奖品。

现在小 A 有 张课堂优秀券和 张作业优秀券,他最多能兑换多少份奖品呢?

输入格式

第一行,两个正整数 ,分别表示小 A 持有的课堂优秀券和作业优秀券的数量。

第二行,两个正整数 ,表示兑换一份奖品所需的两种券的数量。

输出格式

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

输入输出样例 #1

输入 #1
PLAINTEXT2 行
8 8
2 1
输出 #1
PLAINTEXT1 行
5

输入输出样例 #2

输入 #2
PLAINTEXT2 行
314159 2653589
27 1828
输出 #2
PLAINTEXT1 行
1599

说明/提示

对于 的测试点,保证 ,。

对于所有测试点,保证 ,。


题目分析

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

核心思想

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

判定条件:

对于给定的总奖品数 ,假设我们兑换了 份第一种方案( 张课堂券 + 张作业券),那么剩下的 份必须是第二种方案( 张课堂券 + 张作业券)。

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

通过数学推导,我们可以求出 的合法取值范围 。只要这个范围不为空且与 有交集,那么 就是可行的。具体推导如下:

首先,我们有以下两个关于 的不等式:

  1. 课堂券消耗:
  2. 作业券消耗:

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

对于课堂券消耗:

对于作业券消耗:

结合 (式1) 和 (式2),我们得到关于 的范围:

接下来,我们需要根据 和 的大小关系来解出 的范围。

情况一:

此时 为正数,可以直接除以 ,不等号方向不变:

由于 必须是整数,所以 的数学合法取值范围 为:

情况二:

此时 为负数。此时 为正数,可以直接除以 :

由于 必须是整数,所以 的数学合法取值范围 为:

情况三:

此时 。不等式链变为:

这意味着必须满足:

如果这两个条件都满足,那么任意 都是合法的。此时 。如果任一条件不满足,则不存在合法的 。

最终判定条件:

在得到 的数学合法取值范围 后,还需要考虑 必须满足 的条件。 因此,最终有效的 的范围是 ,其中:

如果 ,则表示存在至少一个整数 满足所有条件,即当前的 是可行的。

核心代码逻辑

  1. 输入处理与预处理:首先读取输入的 。为了简化后续的分类讨论,在主函数中预先判断并交换 ,确保满足 。
  2. 二分查找框架:使用 left = 0, right 为可能的理论最大值(如 或 )进行二分查找。每次取中点 mid 作为尝试的总奖品数,调用 check(mid) 函数进行判定。如果可行,尝试更大的答案(left = mid + 1);否则减小范围(right = mid - 1)。
  3. Check 函数判定:check(k) 函数用于判断是否能兑换 份奖品。
    • 若 ,直接检查总需求是否超过资源限制(即 且 )。
    • 若 (已通过预处理保证),根据不等式推导出方案一兑换数量 的合法范围 :
    • 下界 由课堂券限制得出:,且需注意 。
    • 上界 由作业券限制得出:,且需注意 。
    • 最后判断是否存在合法的整数 ,即判断 。

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

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

复杂度

时间复杂度:二分查找的范围大约是 到 ,需要循环约 31 次。每次判定计算量为 。 总时间复杂度为 ,远小于 400ms 的时限。


示例代码

C++71 行
#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的要求下,会超时,但是思路是没问题的,这其实是我最开始想到的方法。

C++43 行
#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;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!