P5815 CQOI2010 扑克牌 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
首先 \(J\) 是个障眼法，稍微思考可知它和数字牌无区别。直接把 \(J\) 当作 \(0\) 号牌即可。也就是 \(n + 1\) 张牌中一次拿 \(n\) 张不同的牌。
容易想到这种拿法相当于，给某种牌添一张，然后在 \(n+1\) 种牌中每种牌都取一张。
又可发现答案具有单调性，二分答案，转化为判定性问题：是否可以拿 \(x\) 次？
拿 \(x\) 次可以分解为：先考虑添 \(x\) 次牌，然后取 \(x\) 次牌。显然等价于添 \(x\) 次牌使得每种牌的数量不少于 \(x\)。
计算一下把每种牌补到 \(x\) 张需要补的牌数是否超过 \(x\) 即可。
算一下二分右边界。答案最大显然应该是 \(n = 2\)，\(m = c_1 =c_2 = 5 \times 10^8\) 的情况，算一下是 \(7.5 \times 10^8\)。这就是右边界了。
时间复杂度 \(\mathcal{O}(n\log c)\)。
\(n\) 的数据范围有点诈骗……
/*
* @Author: crab-in-the-northeast
* @Date: 2022-10-21 10:53:06
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-10-21 10:59:48
*/
#include <bits/stdc++.h>
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
const int maxn = 55;
int a[maxn];
int n;
inline bool check(int x) {
long long t = 0;
for (int i = 0; i <= n; ++i)
if (x > a[i])
t += x - a[i];
return t <= x;
}
int main() {
n = read();
for (int i = 0; i <= n; ++i)
a[i] = read();
int ans = 0;
for (int i = (1 << 30); i; i >>= 1)
if (check(ans + i))
ans += i;
printf("%d\n", ans);
return 0;
}