CQOI2010]扑克牌(二分答案)

题目描述：

n种牌，每种a[i]个，
m张万能牌 ，一次只可以代替一种牌
组成一套的条件：每种牌各一张
求最多组成的套数

题解
直接二分答案（最多能组成的套数）
如果该种牌不够 那么差的牌=mid-a[i]
差几张我们就用几张joker 代替
因为我们要组成mid套牌
每套牌最多有一个joker 所以 设添加t张joker
所以

t<=m&&t<=mid

代码

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=2e5+7;
const ll mod = 1e9+7;
const int N =1e6+3;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,m,a[maxn];
int check(ll x)
{
    ll sum=0;
    rep(i,1,n) if(a[i]<x) sum+=x-a[i];
    if(sum<=m) return 1;
    return 0;
}
int UpMing() {
    n=read();
    m=read();
    rep(i,1,n) a[i]=read();
    ll l=1,r=5000000000,ans;
    while(l<=r) {
        ll mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1;
            }
    out(ans);
    Accept;
}
/*

*/