• 题目考点:二分 + 验证答案
  • 题目内容:给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;
}