题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=1816
题意：有$N$堆牌，第$i$堆牌有$c_i$张牌，还有$M$张$joker$，每一次可以从$N$堆牌中任选一张组成一副牌，或者在任意$N - 1$堆中选择$1$张牌加上一张$joker$组成一副牌，问最多能组成多少副牌。$N \leq 50 , m , c_i \leq 5 \times 10^8$
清流题qwq
每一次的消除一定是在牌最少的一堆使用$joker$，$joker$就等效于这一堆中额外的一张牌。所以先考虑加完$joker$一起减的情况，也就是先把第一少的堆加$joker$直至与第二少的堆牌量相同，然后在前两少的堆中同时加$joker$直至前三堆牌量相同，这么一直做下去，直到$joker$不够或者$N$堆加成一样高，把剩下的$joker$平摊在每一堆上就是最优策略。
然而这样子会有一个问题：一次取牌只能取出一张$joker$，但我们的方案中很有可能一次取出多张$joker$。我们不妨这样考虑：在排序之后，前两堆牌每一次至少会取出一张牌，前三堆牌每一次至少会取出两张牌，以此类推，我们可以得到一个取牌的上界，将这个上界与上面的答案取$min$即可
所以请无视我的高精$QuQ$
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 1e9;
inline ll read(){
ll a = ;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
struct Bignum{
];
Bignum(ll x){
;
){
num[i++] = x % MOD;
x /= MOD;
}
}
Bignum operator +=(ll x){
;
while(x){
num[i] += x % MOD;
if(num[i] > MOD){
num[i + ]++;
num[i] -= MOD;
}
x /= MOD;
i++;
}
return *this;
}
ll operator /(int x){
ll sum = , ans = ;
; i >= ; i--){
sum = sum * MOD + num[i];
ans = ans * MOD + sum / x;
sum %= x;
}
return ans;
}
};
ll num[];
int main(){
freopen("easy.in" , "r" , stdin);
freopen("easy.out" , "w" , stdout);
int N;
ll M;
N = read();
M = read();
; i <= N ; i++)
num[i] = read();
sort(num + , num + N + );
;
ll minN = 1e18 + ;
Bignum sum = num[dir];
] - num[dir] <= M / dir){
M -= (num[dir + ] - num[dir]) * dir;
sum += num[dir + ];
minN = min(minN , sum / dir);
dir++;
}
cout << min(minN , num[dir] + M / dir) << endl;
;
}