二分答案 + 可行性判定(贪心)。二分能整理出多少副牌,计算所需特殊牌数量验证可行性。
OJ: roj
题目 ID: 5007
难度:普及+/提高-
标签:二分答案贪心
创建: 2026-10-08 09:07
更新: 2026-10-08 09:07
形式化题目
给定
本题测试数据系自造数据,出题意图可能与官方原题(如一本通 1671 或 ybtoj)存在细微偏差,但本题解能通过所有数据。
正解
思路
我们要最大化拼出的套牌数,由于“判断能否拼出
假设我们要验证能否拼出
- 对于每一种普通牌
,如果它原有的张数 ,那么不足的部分 必须用特殊牌来顶替。 - 我们把所有种类需要的特殊牌数量累加起来,记为
need。如果need > b,说明特殊牌不够用,拼不出套。 - 还有一个隐藏限制:因为每套牌最多只能用
张特殊牌,所以在拼这 套牌的过程中,至多能消耗 张特殊牌(实际上,对某一种牌需要的顶替次数也不能超过 ,但因为 ,所以 ,单种牌的顶替不会超过 )。因此,如果 need > x,即所需的特殊牌总数超过了总套数,根据抽屉原理,必有一套牌用了至少张特殊牌,这是不合法的。 - 综合以上两点,如果
need <= b且在累加过程中始终有need <= x,说明可以拼出套牌。
二分的上界:所有普通牌加上特殊牌的总数量为
代码
python
import sys
def solve():
input_data = sys.stdin.read().split()
if not input_data:
return
n = int(input_data[0])
b = int(input_data[1])
a = [int(x) for x in input_data[2:]]
sum_a = sum(a)
lo = 0
hi = (sum_a + b) // n + 1
ans = 0
while lo <= hi:
mid = (lo + hi) // 2
need = 0
possible = True
for cards in a:
if cards < mid:
need += mid - cards
if need > mid:
possible = False
break
if possible and need <= b:
ans = mid
lo = mid + 1
else:
hi = mid - 1
print(ans)
if __name__ == '__main__':
solve()cpp
#include <iostream>
#include <vector>
using namespace std;
bool check(long long x, int n, long long b, const vector<int>& a) {
long long need = 0;
for (int i = 0; i < n; ++i) {
if (a[i] < x) {
need += x - a[i];
if (need > x) return false;
}
}
return need <= b;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
long long b;
if (!(cin >> n >> b)) return 0;
vector<int> a(n);
long long sum = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum += a[i];
}
long long lo = 0, hi = (sum + b) / n + 1;
long long ans = 0;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2;
if (check(mid, n, b, a)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << ans << "\n";
return 0;
}复杂度
- 时间复杂度:计算总和需
,二分答案范围在 内,最多循环约 次。每次 check需要遍历个数,时间为 。总时间复杂度为 。对于 足以在规定时限内通过。 - 空间复杂度:需要数组存储每种普通牌的数量,空间复杂度为
。
总结
经典二分答案题目。难点主要在于想到第二个限制条件(每副牌最多用一张特殊牌,从而限制了总的代替次数不能超过要整理的套牌数)。对于极值最优化且正向难以贪心计算的问题,转化为判定问题并结合二分是一种非常基础且重要的思路。