题意

给定 种牌和每种的个数 ，给定 个王牌。有两种方案构成一套牌：

1. 种牌各一张。
2. 种牌各一张加上一张王牌。

问最多可以构成的套牌数目。

题解

一开始写了一个贪心，利用堆每次选择数目最少的种数，用王牌去补。然后超时了，因为 可以很大。

然后开了窍，写了一个二分。大概就是二分答案为 。设 ，表示对第 种牌，王牌补了多少张。那么首先要有 。其次要有 。

时间复杂度为 。可以通过一些技巧降掉一个 。

#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

int n, m, a[55], b[55];
void init(){
    n = read(), m = read();
    REP(i, 1, n)
        a[i] = read();
    sort(a + 1, a + n + 1);
}
void solve(){
    int l = 0, r = a[n] + m;
    while (r > l){
        int mid = (l + r + 1) >> 1;
        ll sum = 0;
        REP(i, 1, n)
            sum += 1ll * max(mid - a[i], 0), 
            b[i] = a[i];
        if (sum > m){
            r = mid - 1;
            continue;
        }
        bool flag = true;
        REP(i, 1, n){
            int t = max(mid - a[i], 0);
            REP(j, 1, n){
                if (i == j) continue;
                if (b[j] < t) {
                    flag = false;
                    break;
                }
                b[j] -= t;
            }
            if (!flag) break;
        }
        if (flag) l = mid;
        else r = mid - 1;
    }
    printf("%d\n", l);
}
int main(){
    init();
    solve();
    return 0;
}