[BZOJ 1816][CQOI 2010] 扑克牌

题目大意

\(n\) 种牌,数目为 \(c_i\),另外有一种特殊的牌:joker,它的数目是 \(m\)。你可以用每种牌各一张来组成一套牌,也可以用一张 joker 和除了某一种牌以外的其他牌各一张组成一套牌。 求每张牌最多只能用在一副套牌里(可以有牌不使用)时套牌组数的最大值。

\(1 \leqslant n \leqslant 50\)

\(1 \leqslant m, \; c_i \leqslant 500,000,000\)

题目链接

BZOJ 1816

题解

二分答案。

判定时,如果有一种牌数量不够,用 joker 补,joker 提前用完则不可行,最大答案为 \(2 max(m, \; c_i)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <algorithm>
const int MAXN = 55;
const int MAXM = 500000000;
int c[MAXN], n, m;
bool check(int x) {
int j = std::min(x, m);
for (int i = 0; i < n; i++) {
if (c[i] < x) {
j -= x - c[i];
if (j < 0) return false;
}
}
return true;
}
int dichotomy() {
int l = 0, r = MAXM << 1;
while (l < r) {
int mid = l + (r - l) / 2 + 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
printf("%d\n", dichotomy());
return 0;
}