牛客—— [CQOI2010]扑克牌 （二分）

牛客—— [CQOI2010]扑克牌 （二分）
原题链接：https://ac.nowcoder.com/acm/problem/19916
##题意：

给n种牌，每种牌c[i]个，和m张万能牌，问最多能够组成多少套牌（包含所有的种类）

思路：

考虑二分答案，贪心进行检验。

如果最多能够构成x套牌，每种牌至少x张，如果c[i]<x的话就要用万能牌去补齐。

在check的时候，当c[i]<x时才使用万能牌，当万能牌不够时说明该答案偏大。

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>PII;
#define I_int ll
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    cout<<endl;
}

const int maxn=1e6+10;
ll n,m;
ll c[maxn];

bool check(ll mid){
    ll tmp=min(mid,m);
    for(int i=1;i<=n;i++){
        tmp-=max(mid-c[i],0ll);
        if(tmp<0) return 0;
    }
    return 1;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) c[i]=read();
    ll l=1,r=1e9,res;
    while(l<=r){
        ll mid=(l+r)/2;
        if(check(mid)) res=mid,l=mid+1;
        else r=mid-1;
    }
    out(res);
    return 0;
}