二分答案 + P8800 [蓝桥杯 2022 国 B] 卡牌 - 题解

题解：卡牌问题

题目传送门：P8800 [蓝桥杯 2022 国 B] 卡牌

一、题目描述

小明有n种卡牌，每种卡牌有a_i张。他可以用m张空白牌制作任意卡牌，但第i种卡牌最多只能制作b_i张。问最多能凑出多少套"完整卡牌"（每套包含每种卡牌各一张）。

二、题目分析

这是一个典型的二分答案问题。我们需要找到最大的套数x，使得我们可以通过使用空白牌，让每种卡牌的数量都至少达到x张，且使用的空白牌总数不超过m张。

三、解题思路

1. 二分搜索：我们可以在可能的套数范围内进行二分搜索，检查某个套数x是否可行。
2. 可行性检查：对于每个候选的x，计算每种卡牌需要补充的数量（x - a_i），但要不超过b_i的限制，且总和不超过m。

四、算法讲解

算法采用二分答案策略：

1. 排序：虽然题目没有明确要求，但将卡牌按现有数量排序可能有助于优化（但原代码中排序实际上不影响最终结果）。
2. 二分框架：在可能的套数范围[0, max_a + m]内进行二分搜索。
3. 检查函数：对于中间值mid，计算将所有卡牌补充到至少mid张所需空白牌数，检查是否满足条件。

以样例为例：

• 输入：n=4, m=5, a=[1,2,3,4], b=[5,5,5,5]
• 检查x=3：
  • 需要补充：2(1→3),1(2→3),0(3→3),0(4→3)
  • 总空白牌使用=3 ≤ 5，且每个补充不超过b_i限制
• 检查x=4：
  • 需要补充：3(1→4),2(2→4),1(3→4),0(4→4)
  • 总空白牌使用=6 > 5，不可行
• 因此最大可行套数是3

五、代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int n, m;
struct node {int a, b;
} arr[N];// 排序函数，按现有卡牌数量升序排列
bool cmp(node c, node d) {return c.a < d.a;
}// 检查是否能凑出x套牌
bool check(int x) {int cnt = 0;for (int i = 1; i <= n; i++) {int tem = x - arr[i].a;if (tem < 0)  // 现有牌已足够，不需要补充continue;else if (tem > arr[i].b)  // 需要补充的数量超过b_i限制return false;else {cnt += tem;  // 累加需要的空白牌数量}}return cnt <= m;  // 总空白牌使用量不超过m
}void solve() {cin >> n >> m;for (int i = 1; i <= n; i++)cin >> arr[i].a;for (int i = 1; i <= n; i++)cin >> arr[i].b;sort(arr + 1, arr + 1 + n, cmp);  // 按现有数量排序// 二分查找最大可行套数int l = -1, r = 1e6;  // 初始范围设置while (l + 1 != r) {int mid = l + r >> 1;if (check(mid))l = mid;elser = mid;}cout << l;
}signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

六、重点细节

1. 二分边界：初始左边界设为-1，右边界设为1e6，确保覆盖所有可能情况。
2. 检查函数：必须同时满足两个条件：(1)每种卡牌补充不超过b_i限制；(2)总补充数不超过m。
3. 排序：虽然排序不是必须的，但可能在某些优化策略中有用（尽管原代码中并未利用排序特性）。

七、复杂度分析

1. 时间复杂度：O(n log(max_answer))，其中二分次数为log(max_answer)，每次检查需要O(n)时间。
2. 空间复杂度：O(n)，用于存储卡牌信息。

八、总结

本题通过二分答案的方法高效地解决了最大套数问题。关键在于设计合理的检查函数来判断某个套数是否可行。算法的时间复杂度能够很好地处理题目给出的数据规模限制（n ≤ 2×10^5）。

这种二分答案的思路在解决"最大化最小值"或"最小化最大值"类问题时非常有效，是算法竞赛中的重要技巧。