[CQOI2010]扑克牌（持续写二分水题）

题意

你有种牌，第种牌的数目为。另外有张万能牌，万能牌可替换任何一张牌。种牌各一张可以组成一套，每套最多使用万能牌一次，问最多能组成多少套。

思路

显然二分答案。对于最多使用万能牌一次，判断每次二分答案时，要使用万能牌的总数是否超过了当前的套数。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+5;
ll n,k;
ll a[maxn], b[maxn];
ll check(ll mid, ll k) {
    ll ans=0;
    for(ll i=0;i<n;i++) {
        if(mid>a[i]) ans+=mid-a[i];
    }
    return ans<=min(k,mid);
}
int main() {
    scanf("%lld%lld",&n,&k);
    for(ll i=0;i<n;i++) scanf("%lld",&a[i]);
    ll l=0,r=1e9,mid,ans=-1;
    while(l<=r) {
        mid=(l+r)>>1;
        if(check(mid, k)) ans=max(ans,mid),l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",ans);
}