GESP 题解库 / 5 级题解 / [GESP202506 五级] 奖品兑换 · 第 8 / 23 题
GESP202506 五级 · P13013 · 中等

奖品兑换

两种券分别 n、m 张,每份奖品需要 a、b 张(两种搭配皆可),求最多兑换份数。

📊
n, m ≤ 10⁹
券的数量
🔢
long long
数值类型
⚡
O(log n)
时间复杂度
🎯
二分答案 + 线性约束
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

可用 a 张课堂券 + b 张作业券 兑换一份奖品,或 b 张课堂券 + a 张作业券 兑换一份奖品。

现在有 n 张课堂券和 m 张作业券,求最多能兑换多少份奖品。

💡
人话翻译:每份奖品的"券配方"有两种:(a, b) 或 (b, a)。设用第一种配方兑换 x 份、第二种兑换 y 份,则要满足两个不等式;我们要最大化 x + y。这是一个"二分答案 + 检验可行性"的典型题。

🔍 关键词提取

二分答案可行性检验线性约束整数解

已知条件

项目说明
输入第一行 n、m(课堂券、作业券数量);第二行 a、b
输出最多兑换的奖品份数
数据范围1 ≤ a, b ≤ 10⁴,1 ≤ n, m ≤ 10⁹
两种配方(a, b) 或 (b, a)
目标最大化奖品份数

需要解决的问题

02
思维导图
整理解题思路的全貌
📐 二分答案 + 解线性区间
🎯 二分什么
二分答案 k(奖品份数)
检验"能否兑换 k 份"
k 越大越难,有单调性
上界取 (n+m)/(a+b) 量级
🧮 检验方法
设配方 (a,b) 用 x 份
配方 (b,a) 用 k−x 份
代入两个不等式
化成 x 的取值范围
📊 解不等式
x·a + (k−x)·b ≤ n
x·b + (k−x)·a ≤ m
整理成 L ≤ x ≤ R
L ≤ R 且区间含整数 → 可行
⚠️ 易错点
用 int 溢出(n 可达 10⁹)
不等式方向搞反
忘记 x 要在 [0, k] 内
区间判空时忽略整数性
03
样例手算推导
样例 1 的二分检验过程

🧮 样例 1:n = 8,m = 8,a = 2,b = 1

每份奖品需要 2 + 1 = 3 张券(两种配方合计都是 3 张),总券数 16,所以最多不可能超过 ⌊16 / 3⌋ = 5 份。

1
检验 k = 5

设配方 (2,1) 用 x 份,配方 (1,2) 用 5 − x 份

课堂券:2x + 1×(5−x) = x + 5 ≤ 8 → x ≤ 3

作业券:1×x + 2×(5−x) = 10 − x ≤ 8 → x ≥ 2

所以 x ∈ [2, 3],有整数解 ✅

✅ k = 5 可行

2
检验 k = 6

课堂券:2x + (6−x) = x + 6 ≤ 8 → x ≤ 2

作业券:x + 2(6−x) = 12 − x ≤ 8 → x ≥ 4

要求 x ≤ 2 且 x ≥ 4 → 无解

所以 k = 6 不可行

❌ k = 6 不可行

kx 的下界x 的上界是否有整数解
52(来自作业券)3(来自课堂券)✅ 有
642❌ 无(下界 > 上界)

答案 5 ✓

🔑
检验的核心是把"二元一次不等式组"化成一元区间。因为 y = k − x,两个不等式都只含 x,整理后得到 L ≤ x ≤ R;只要 L ≤ R 且 [L, R] 与 [0, k] 有整数交集,就可行。这一步判断是 O(1) 的,所以整体可以二分。

🧮 样例 2:大数据的验算

n = 314159,m = 2653589,a = 27,b = 1828,答案 1599。

1
上界估算

每份奖品两种配方合计都是 a + b = 1855 张券

总券数 = 314159 + 2653589 = 2967748

⌊2967748 / 1855⌋ = 1599.86… → 上界 1599

所以答案不超过 1599

上界 1599

2
检验 k = 1599 是否可行

课堂券约束:27x + 1828(1599−x) ≤ 314159

1828×1599 = 2922972,所以 2922972 − 1801x ≤ 314159

→ 1801x ≥ 2608813 → x ≥ 1448.5 → x ≥ 1449

作业券约束:1828x + 27(1599−x) ≤ 2653589

27×1599 = 43173,所以 43173 + 1801x ≤ 2653589

→ 1801x ≤ 2610416 → x ≤ 1449.4 → x ≤ 1449

两者合起来:x = 1449,唯一解 ✅

✅ k = 1599 可行,且它等于上界,所以是答案

答案 1599 ✓

⚠️
注意变量的数量级:n 和 m 可达 10⁹,k × b 这类乘积会达到 10⁹ × 10⁴ = 10¹³,远超 int 范围,必须用 long long。这也是本题一个常见失分点。
04
解法对比
二分答案 vs 枚举某一方份数

⚔️ 解法对比

🟢 二分答案 + O(1) 检验(推荐) 推荐

二分 k,每次用一元区间判断可行性

  • 时间 O(log(n+m))
  • 约 60 次检验
  • 检验是 O(1)
  • 代码 20 行
💡
为什么可以二分:如果 k 份可行,那么少于 k 份也一定可行(少兑换几份总不会更难),所以可行性关于 k 单调,可以二分。

🟠 枚举 x 的取值

枚举配方 (a,b) 用多少份,再算配方 (b,a) 最多用多少份

  • 枚举量可能达 10⁹
  • 超时
  • 但若 a、b 较小则可行
  • 不如二分稳妥
⚠️
注意:本题 n、m 可达 10⁹,而 a、b ≤ 10⁴,所以 x 的取值可能达到 10⁹ 量级,枚举会超时。(题目特意说明"时限下降为 400 毫秒",就是在提示需要 O(log) 的做法。)

📈 性能对比

方案复杂度可行性
二分答案O(log(n+m))✅ 稳过
枚举 xO(n / a)❌ 可能超时
05
算法流程图
二分份数并用区间检验
开始读入 n、m、a、b;设二分区间 lo = 0,hi = (n + m) / (a + b)当 lo <= hi 时取 mid = (lo + hi) / 2令 y = mid − x,把两个不等式整理成 x 的区间 [L, R]区间内存在满足 0 ≤ x ≤ mid 的整数吗?是 ✓可行:记录答案,lo = mid + 1否 ✗不可行:hi = mid − 1输出记录的最大可行份数结束二分区间还有效 → 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🎁 奖品兑换计算器

输入 n、m 和 a、b,程序会用二分法求出最多能兑换的份数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

long long n, m, a, b;

// 判断能否兑换 k 份
bool can(long long k) {
    // 设用配方 (a,b) 兑换 x 份,则配方 (b,a) 兑换 k-x 份
    // 约束1:a*x + b*(k-x) <= n   ->   (a-b)*x <= n - b*k
    // 约束2:b*x + a*(k-x) <= m   ->   (b-a)*x <= m - a*k
    long long L = 0, R = k;

    // 处理约束1
    long long c1 = a - b, r1 = n - b * k;
    if (c1 > 0) R = min(R, r1 / c1);
    else if (c1 < 0) L = max(L, (r1 + c1 + 1) / c1);   // 注意负数向上取整
    else if (r1 < 0) return false;

    // 处理约束2
    long long c2 = b - a, r2 = m - a * k;
    if (c2 > 0) R = min(R, r2 / c2);
    else if (c2 < 0) L = max(L, (r2 + c2 + 1) / c2);
    else if (r2 < 0) return false;

    return L <= R;                 // 区间非空即可行
}

int main() {
    scanf("%lld %lld", &n, &m);
    scanf("%lld %lld", &a, &b);

    long long lo = 0, hi = (n + m) / (a + b) + 1, ans = 0;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        if (can(mid)) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么二分上界取 (n+m)/(a+b)?因为每兑换一份奖品,不论用哪种配方,都要消耗 a + b 张券(只是课堂券和作业券的分配不同)。所以份数不可能超过 ⌊(n+m)/(a+b)⌋。这个上界非常紧,能减少二分次数。

📖 关键几行怎么看

代码作用为什么这样写
(a-b)*x <= n - b*k整理约束把 y = k − x 代入消去一个变量
if (c1 > 0) R = min(R, r1/c1)上界正系数时解出 x ≤ r1/c1
L = max(L, (r1+c1+1)/c1)下界(负数除法的向上取整)C++ 整数除法向零取整,负数要手动调整
return L <= R;可行性区间非空说明存在整数 x
⚠️
三个坑:① 用 int(k × b 可达 10¹³,必须 long long);② 负系数的"向上取整"处理错(C++ 除法向零取整);③ 忘记 x 还要满足 0 ≤ x ≤ k(初始化 L、R 时已包含)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
8 8
2 1
5题面样例 1
314159 2653589
27 1828
1599题面样例 2(大规模)
3 3
1 1
3两种配方相同,每份只需 2 张券
1 100
1 100
1配方 (1,100) 用一次
1000000000 1000000000
1 1
1000000000每份 2 张券,共 2 × 10⁹ 张,可兑 10⁹ 份
✅
自查清单:① 用 long long 吗?② 区间非空的判断对吗?③ 二分的单调性用对了吗?

🚨 易错点清单

⚠️
用 int:k × b 可达 10⁹ × 10⁴ = 10¹³,必须用 long long。
⚠️
负系数取整错误:C++ 整数除法向零取整,负系数解不等式时要手动实现"向上取整"。
⚠️
忘记二分:枚举 x 的取值可能达 10⁹,会超时。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(log(n+m))
空间复杂度
O(1)
n, m 最大
10⁹
二分次数
约 60 次

时间怎么算的?

空间都用在哪?

只用几个变量。

✅ 几十次检验,瞬间完成。题目提示"时限下降为 400 毫秒",正是在提示要用 O(log) 的做法。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 二分答案的通用模板(求最大可行值)
long long lo = 0, hi = 上界, ans = 0;
while (lo <= hi) {
    long long mid = (lo + hi) / 2;
    if (判断可行(mid)) { ans = mid; lo = mid + 1; }   // 可行 -> 试试更大
    else hi = mid - 1;                                 // 不可行 -> 调小
}

// 本题的可行性判断本质是"一元线性不等式组是否有整数解"
// (a-b)*x <= n - b*k
// (b-a)*x <= m - a*k
// 这类问题可以推广到更多约束的线性规划(小规模)

// 整数除法的取整方向
// C++: 7 / 2 = 3,  -7 / 2 = -3   (向零取整)
// 向上取整的写法: (x + d - 1) / d   (当 x >= 0, d > 0)
// 负数的向上取整: (x + d + 1) / d 需要仔细验证

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
二分答案单调性 + O(1) 检验最大值最小、最小值最大类问题
线性约束化简代入消元变成区间二元一次不等式组、小规模线性规划
取整方向C++ 除法向零取整所有涉及"最多/最少整数"的题
🌟
思考题:如果题目改成"有三种兑换配方"(比如还有 (a, c) 等),二分的框架还成立吗?(提示:成立——可行性仍然关于 k 单调。但每次检验就从"一元不等式组"变成二元或多元,O(1) 检验不再容易,可能需要枚举其中一个变量(如果能枚举)或者做小规模线性规划。这说明二分只是"外层框架",难点在于内层的可行性检验。)