[CQOI2010]扑克牌(二分)

题目：

你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。

做法：

二分套牌的数量，将问题转化成判定行问题。为什么可以这么做呢？因为若能组成x套牌，必定能组成x-1套牌，有一个临界点在里面。二分的check，我们可以算出mid套牌需要几张joker，若need≤m且need≤x，就是可行。第一个判断条件很显然，第二个判断条件是基于一套牌只能由一张joker的限制。

代码：

#include <bits/stdc++.h>
#define debug(a) cout << #a ": " << a << endl
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int N = 55;
const int inf = 0x3f3f3f3f;
int n, m, c[N];
bool check(int x){
    ll need = 0;
    for (int i = 1; i <= n; ++i){
        need += max(x-c[i], 0);
    }
    return need <= m && need <= x;
}
int main(void){    
    IOS;
    cin >> n >> m;
    int mn = inf;
    for (int i = 1; i <= n; ++i){
        cin >> c[i];
        mn = min(mn, c[i]);
    }
    int l = 0, r = mn+m, ans = 0;
    while (l <= r){
        int mid = (l+r) >> 1;
        if (check(mid)){
            ans = mid;
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    cout << ans << endl;
    return 0;
}