题意

有 $n$ 种普通牌和王牌，其中王牌有 $m$ 张，第 $i$ 种普通牌有 $c_i$ 张。一套牌可以由 $n$ 种普通牌各一张来组成，也可以由 $n-1$ 种普通牌各一张再加上一张王牌组成，问最多能组成多少套牌。

$\texttt{Data Range:}1\leq n\leq 50,1\leq m,c_i\leq 5\times 10^8$

题解

先扯几句题外话。

神 WYXkk 的题解由于二分上界的问题会在某些毒瘤数据上直接返回二分上界，比如如下数据：

3 500000000
500000000 500000000 500000000

该组数据正确答案为 $666666666$，而神 WYXkk 的代码输出了 $600000000$，构造方案如下：

$166666666$ 组 $\{1,2,3\}$，$166666666$ 组 $\{1,2,J\}$，$166666666$ 组 $\{1,J,3\}$，$166666666$ 组 $\{J,2,3\}$。

这个时候 $1,2,3,J$ 四种牌每种都剩下两张能凑出最后两组，所以答案为 $666666666$。

注意到这个题的话可以二分答案。考虑转化一下组一套牌的过程，相当于每种牌都先拿一张出来，再丢一张回去。于是 check 的过程可以考虑每种牌都拿 $x$ 张出来丢多少张回去，然后没了。

一个注意的点是二分的右端点应该至少为 $750000000$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51;
ll n,l,r,mid,res;
ll c[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll check(ll mid)
{
	li res=0;
	for(register int i=0;i<=n;i++)
	{
		res+=max(mid-c[i],0);
	}
	return res<=mid;
}
int main()
{
	n=read(),c[0]=read(),r=8e8;
	for(register int i=1;i<=n;i++)
	{
		c[i]=read();
	}
	while(l<=r)
	{
		mid=(l+r)>>1;
		check(mid)?l=mid+1,res=mid:r=mid-1;
	}
	printf("%d\n",res);
}