两种券分别 n、m 张,每份奖品需要 a、b 张(两种搭配皆可),求最多兑换份数。
可用 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) |
| 目标 | 最大化奖品份数 |
(a,b) 兑换 x 份,配方 (b,a) 兑换 y 份x·a + y·b ≤ n 且 x·b + y·a ≤ my = k − x,则两个不等式都变成关于 x 的线性约束,解出 x 的允许区间,看区间是否有整数每份奖品需要 2 + 1 = 3 张券(两种配方合计都是 3 张),总券数 16,所以最多不可能超过 ⌊16 / 3⌋ = 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 可行
课堂券: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 不可行
| k | x 的下界 | x 的上界 | 是否有整数解 |
|---|---|---|---|
| 5 | 2(来自作业券) | 3(来自课堂券) | ✅ 有 |
| 6 | 4 | 2 | ❌ 无(下界 > 上界) |
答案 5 ✓
y = k − x,两个不等式都只含 x,整理后得到 L ≤ x ≤ R;只要 L ≤ R 且 [L, R] 与 [0, k] 有整数交集,就可行。这一步判断是 O(1) 的,所以整体可以二分。n = 314159,m = 2653589,a = 27,b = 1828,答案 1599。
每份奖品两种配方合计都是 a + b = 1855 张券
总券数 = 314159 + 2653589 = 2967748
⌊2967748 / 1855⌋ = 1599.86… → 上界 1599
所以答案不超过 1599
上界 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 ✓
long long。这也是本题一个常见失分点。二分 k,每次用一元区间判断可行性
枚举配方 (a,b) 用多少份,再算配方 (b,a) 最多用多少份
x 的取值可能达到 10⁹ 量级,枚举会超时。(题目特意说明"时限下降为 400 毫秒",就是在提示需要 O(log) 的做法。)| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 二分答案 | O(log(n+m)) | ✅ 稳过 |
| 枚举 x | O(n / a) | ❌ 可能超时 |
输入 n、m 和 a、b,程序会用二分法求出最多能兑换的份数。
点按钮开始 →
#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 时已包含)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
8 8 | 5 | 题面样例 1 |
314159 2653589 | 1599 | 题面样例 2(大规模) |
3 3 | 3 | 两种配方相同,每份只需 2 张券 |
1 100 | 1 | 配方 (1,100) 用一次 |
1000000000 1000000000 | 1000000000 | 每份 2 张券,共 2 × 10⁹ 张,可兑 10⁹ 份 |
只用几个变量。
✅ 几十次检验,瞬间完成。题目提示"时限下降为 400 毫秒",正是在提示要用 O(log) 的做法。
// 二分答案的通用模板(求最大可行值) 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) 检验不再容易,可能需要枚举其中一个变量(如果能枚举)或者做小规模线性规划。这说明二分只是"外层框架",难点在于内层的可行性检验。)