题解 | #[CQOI2010]扑克牌#

• 题目考点：二分 + 验证答案
• 题目内容：给n种牌和一种Joker牌，问能合成几套牌，其中每一套牌要包含n种不同的牌（其中给定的n种牌中若有一种不够用，可以用Joker代替，Joker也只能在一套牌里出现一次）。
• 题目分析：二分答案，例如题目样例：

3 4
1 2 3
//即第一种牌1张，第二种2张，第三种三张，joker 4 张，每套牌3张，至少含三种不同的牌

我们来模拟验证答案为2、3、4时的答案：

观察到以下情形：
1、如图①和②，当第一种牌或者第二种牌不够用时，可以用joker替换；
2、如图①和②，使用的joker小于4，说明够用，则ans = 2 或 ans = 3能够组成 ；
3、如图③，当使用的joker大于m = 4，则说明joker不够用，不能组成；
4、如图③，当使用的joker大于ans = 4，则说明joker在不止一组中出现过，不符合题意。
因此代码如下：

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 55;
int a[N];
int n, m;

bool jud(int mid)
{
    LL ans = 0; //ans记得开logn long，有10分卡数据范围
    for(int i = 1; i <= n; i++)
        if(a[i] < mid) ans += mid - a[i];  //对应情形1
    //cout<<' '<<ans << ' '<< (ans <= m && ans <= mid)<<'\n';
    return ans <= m && ans <= mid; //对应情形2、3、4
}

int main()
{
    scanf("%d%d", &n, &m);
    int maxx = 0;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]), maxx = max(maxx, a[i]);

    int l = 1, r = maxx * 2;
    while(l < r)
    {
        int mid = l + r + 1 >> 1; //二分l = mid需要给和+1
        //cout<<mid <<' '<<l <<' '<< r;
        if(jud(mid)) l = mid;
        else r = mid - 1;
    }
    cout<< l;
    return 0;
}