题意

你有种牌,第种牌的数量为,除此之外还有一种特殊的牌,他的数量为。你可以用每种牌各一张来组成一套牌,也可以用一张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;
}