[CQOI 2010] 扑克牌

题目大意

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

1n501 \leqslant n \leqslant 50

1m,  ci500,000,0001 \leqslant m, \; c_i \leqslant 500,000,000

题目链接

【CQOI 2010】扑克牌

题解

二分答案。

判定时,如果有一种牌数量不够,用 joker 补,joker 提前用完则不可行,最大答案为 2max(m,  ci)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;
}