[二分] bzoj1816: [Cqoi2010]扑克牌

bzoj1816: [Cqoi2010]扑克牌 ：http://www.lydsy.com/JudgeOnline/problem.php?id=1816

这是一道非常苟的二分
二分方案数然后验证
有多少种方案就尽量用多少次joker
不用某一张可以看作用joker代替某一张
这样的话要用joker的次数为mid-a[i]
tot统计一下 因为joker可以不用完 那么判断一下是否小于等于mid和m就可以了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long a[60];
int n,m;
bool solve(long long x)
{
    long long tot=0;
    for (int i=1;i<=n;i++) //选择不用那一种  
        if (x>a[i]) tot+=x-a[i]; //每一次每一种用一张 所以有这种牌的方案数为a[i] 所以不用这种牌的方案数=要用joker代替这种牌多少次 也就是x-a[i] 
    if (tot>m) return false; 
    if (tot>x) return false;//tot统计出来用了多少次joker joker可以不用完
    return true; 
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    long long l=0,r=1000000000,ans=0;
    while (l<=r)
    {
        int mid=(l+r)/2;//枚举方法数  有这么多种方案就尽量每一个方案都用一张joker 这样最多就用了mid张joker  
        if (solve(mid))//验证方案数 
        {
            ans=mid;l=mid+1;
        }
        else r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}