【每日一题】扑克牌

解题思路

有 种牌，第 种牌有 个，另有 个 joker 牌，求最多可以组成多少套牌？
一副套牌中包含 个牌，每个牌都不相同。

假设可以组成 副套牌，如果 ，可由 joker 牌补充。需要补充的牌数总和应 。
使用二分法确定满足条件的 的最大值。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n, m;

bool cards(vector<int>& c, int x){
    int tmp = min(m, x);
    for(int i=0; i<n; ++i){
        if(c[i] < x)
            tmp -= x - c[i];
        if(tmp < 0)
            return false;
    }
    return true;
}

int main(){
    cin >> n >> m;
    vector<int> c(n);
    for(int i=0; i<n; ++i)
        cin >> c[i];

    sort(c.begin(), c.end());
    int left = c[0];
    int right = c.back() + m / n;
    int ans = left;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(cards(c, mid)){
            left = mid + 1;
            ans = max(ans, mid);
        }
        else
            right = mid - 1;
    }
    cout << ans << endl;
    return 0;
}