题解 P5815 【[CQOI2010]扑克牌】

· · 题解

显然二分 + 贪心；

每次二分一个套牌数目，设它为 std 。贪心的使用 joker 。对于每种牌，如果它的数目 c_{i} 大于等于 std ，那么不用管它，这种牌的数目是足够的。如果小于 std ，那我们就要使用 joker 了（能放则放，贪心思想）。

我们用一个 tmp 容器记录一下 joker 使用的次数，然后考虑 tmp 等于多少时，这个 std 不符合条件，也就是求一下 tmp 的限制条件。

第一个是因为最多只有 m 张 joker ，第二个是因为每套牌中只能出现一张 joker 。

那为什么这么贪心的放牌是对的呢？因为我们有一个限制条件 tmp <= std ，我们不管 joker 到底出现在哪，只管用了几张，只要这套牌用了 joker ，这套牌别的位置就用给出的牌填上去。那如果别的牌不够呢，填不上去咋办？

假设我们现在紫色的牌只有四张，黑牌代表 joker ，如果要填满就得用两张 joker ，我们发现第三套牌（第三行）出现了两张 joker ，不符合题意了，但是这时候 tmp > std ，我们就可以直接判断不合法了。

下面是代码：

#include <iostream>
#include <cstdio>
#include <cctype>
#define mid ((l + r + 1) >> 1)

using namespace std;

inline long long read() { //快读
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 55, inf = 7e8 + 5e7 + 1; //自己瞎试了试 
int n, m, l, r;
int c[N];

bool judge(int std) {
    int tmp = 0, rest = std;
    for(int i = 1;i <= n; i++) {
        if(c[i] >= std) continue;
        tmp += (std - c[i]); rest -= (std - c[i]); //两个判断条件
        if(tmp > m || rest < 0) return 0;
    }
    return 1;
}

int main() {

    n = read(); m = read();
    for(int i = 1;i <= n; i++) c[i] = read(); 
    l = 1, r = inf;
    while(l < r) { //二分套牌数目
        if(judge(mid)) l = mid;
        else r = mid - 1;
    }
    printf("%d", l);

    return 0;
}

个人感觉挺好理解的，如果有不对的地方还希望dalao纠正QWQ