X014 卡牌
大约 2 分钟
X014 卡牌
【算法】 二分答案
【C++】 二分、贪心验证
【难度】 普及/提高−
一、题目简述
有 种卡牌,第 种卡牌已有 张。一套完整的卡牌需要每种各一张。现在有 张空白牌,可以在上面手写任意种类的卡牌,但第 种卡牌最多手写 张。求最多能凑出多少套完整的卡牌。
数据范围:,,。
二、解题思路
1. 为什么能用二分
单调性:套数 越多,需要补的空白牌就越多。如果 套可行,那么 套一定也可行(需要的空白牌更少)。判定结果呈现单调性。
2. check 函数设计
check(x):对于第 种卡牌:
- 已有 张,需要 张
- 如果 ,不需要空白牌
- 如果 ,需要 张空白牌
但有两个约束:
- 总空白牌限制:所有种类的空白牌需求之和不能超过
- 单种限制:第 种最多手写 张,所以 不能超过 (否则直接失败)
3. 二分范围
- 左边界:(一套都凑不出是可能的)
- 右边界:(极端情况: 小、 极大、 极大)
使用 long long 避免溢出。
4. 手动模拟
假设 3 种卡牌,已有 [2, 3, 1],空白牌 ,手写上限 [1, 2, 2]:
| 套数 | 种1需补 | 种2需补 | 种3需补 | 总需 | 是否超限 | 判定 |
|---|---|---|---|---|---|---|
| 3 | 1(=3-2) | 0(=3-3) | 2(=3-1) | 3 | 种3不超2 ✅ | ✅ |
| 4 | 2(=4-2) | 1(=4-3) | 3(=4-1) | 6 | 种3超2 ❌ | ❌ |
答案 = 3 套。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
long long a[N], b[N], n, m;
bool check(long long x) {
long long need = 0;
for (int i = 1; i <= n; i++) {
long long diff = x - a[i];
if (diff > b[i]) return false; // 单种手写超限
if (diff > 0) need += diff;
}
return need <= m;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
long long l = 0, r = 2e14, ans = 0;
while (l <= r) {
long long mid = (l + r) / 2;
if (check(mid)) { ans = mid; l = mid + 1; }
else r = mid - 1;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,其中 是二分范围(约 ),。每次
check需要遍历 种卡牌。 - 空间复杂度:,存储两个数组。
