NC19916 CQOI2021 扑克牌

题意

你有种牌，第种牌的数量为，除此之外还有一种特殊的牌，他的数量为。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌，请问最多能组成多少套牌

思路

看到这个题目我有一种俄罗斯方块的感觉，用joker或者原本的格子把一行填满，就组成了一套牌。但它有一条特殊的规则：一套牌中，joker最多只能代替一种牌出现
例如：

虽然有999张joker足以填满所有格子，但因为一套牌中，joker最多只能代替一种牌出现，这里最多只能组成套牌

那么如何正确的计算套牌的数量呢？
我们仍可以按这个思路走（其实差的有点远）

我们从最下面的行开始，往每一行里继续塞格子（也就是joker），尽可能把行填满，填满以后也就得到了一套牌。
塞joker格子的时候我们遵循两个规则：

1. 塞进去的joker数量要永远小于等于m
2. 每一行最多只能塞一个joker

但其实呢，这个格子并不像俄罗斯方块里那样必须往下掉落，格子在它所在的列里是可以移动的。

*下面部分写的不好，建议搭配代码以及亲手画图理解
例如：

这样来看，我们移动了第一列的格子以后能把更多的行塞满。

原本是每一行最多只能塞一个joker，但现在每行的格子可能会发生变化，我们可以把原本要塞很多joker的行拆成多行来塞入joker，用原有的格子来把空白格子分割开（如上图）。
我们再根据题目“可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌”做出调整，我们可以把这个规则修改成从第行到第行塞入的joker总数不能大于（即每行最多塞入一个，但一行需要塞入多个joker时可以从其他原本就被塞满的行中拆出蓝色格子放进去，实现每一行都正好需要塞入一个joker）

根据上述的规则，我们可以判断能否组成t副套牌
然后就可以用二分+检验的方式找到最多组成的套牌数量

一个小坑

二分时上界应该从开始
因为对于的情况，当每种牌都有张，joker有张时，可以组成套牌。
如图：蓝色为普通牌，绿色为joker

代码

*请仔细阅读上方题解和代码中的注释

#include <iostream>

using namespace std;

int main() {
    int n;  //牌的种数
    int m;  //joker的数量
    cin >> n >> m;
    int c[n + 1];   //每种牌的数量
    int maxC;   //某种牌数量的最大值
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        maxC = max(c[i], maxC);
    }
    //二分找出最多组成的套牌数目
    //这里right=maxC*2 因为允许每套牌都用一个joker替代其中一种
    int left = 0, right = maxC * 2, mid;
    while (left <= right) {
        //mid是最多组成的套牌数目
        mid = (left + right) >> 1;
        int usedJoker = 0;    //使用掉的joker数量
        for (int i = 1; i <= n; ++i) {
            //如果牌数足够则跳过
            if (c[i] >= mid)continue;
            //牌数不够joker凑
            usedJoker += mid - c[i];
            //用的joker大于实际的joker或者大于组成的套数（至少有两种牌数量不足）就退出
            if (usedJoker > m || usedJoker > mid)break;
        }
        //joker有多则可能能组成更多套牌
        //joker不够则可能组成更少套牌
        //且每一套最多只能用一张joker
        if (usedJoker <= m && usedJoker <= mid)left = mid + 1;
        else right = mid - 1;
    }
    cout << left - 1;
}