BZOJ 1816 扑克牌

题目大意

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

这道题真的很难去想……但是我们发现最多啥的，求方案啥的，当然首先要看看有没有单调性……我们发现：巧了，确实应该有，于是我们就可以使用二分的方法来解决。

二分板子再写错我就可以Go Die了……真是GG呢QwQ

#include <bits/stdc++.h>
using namespace std;
int n,m,a[110],maxnum;
bool check(int target)
{
    int tmp = 0,tmpb=min(target,m);
    for(int i = 1;i <= n;++i)
        if(target - a[i]>0)
        {
            tmp += target - a[i];
            if(tmp>tmpb) return false;
        }
    return true;
}
int bifind()
{
    int l = 0, r = maxnum+m+1,mid;
    while(l < r)
    {
        mid = (l + r) >> 1;
        if(check(mid)) l = mid+1;
        else r = mid;
    }
    return l-1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        maxnum=max(maxnum,a[i]);
    }
    printf("%d",bifind());
    return 0;
}

二分答案还有第二个板子……

int bisection()
{
	long long l=0,r=1000*n,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	return r;
}