题解37 [CQOI2010] 扑克牌

思路：一道最值问题，故尝试把组成牌的套数当作二分对象，假设需要组成牌的套数过多就一定组不成（有明显的区分点）。故使用二分枚举+验证，现在重点在于如何验证？这要用到抽屉原理的知识。每套牌不能有重复的，则最多一张joker，如果need>套数，则一定有重复的。且给出的joker数量要足够 AC代码：

#include<iostream>
using namespace std;
#define int long long
int a[60];
int n,m;
bool solve(int x)
{
    int need=0;
    for(int i=1;i<=n;++i)
    {
        if(a[i]<x) {need+=x-a[i];}
    }
    return need<=m && need<=x;//1.joker数量够，2.且根据抽屉原理，每套牌不能有重复的，则最多一张joker，如果need>套数，则一定有重复的
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
  //因为二分是log2 n级别，与其算出可能达到的最大值（用max（）），还不如直接根据数据算出最大值
    int l=1,r=1e9,mid;//如果n=2，那么每套牌只要两张牌，此时若joker=cn=5e8，那么最大就是1e9
    while(l<r)
    {
        mid=(l+r+1)>>1;//求最大类比于求满足<=x的最后一个
        if(solve(mid)) {l=mid;}
        else {r=mid-1;}
    }
    cout<<l;
    return 0;
}