【每日一题】扑克牌

题意

有n种扑克牌，每种有ci个。还有m张王牌。可以代替其中任一张。最多可以造出几个套牌（每副牌只能用一次）。

solution

典型的二分答案，每副牌只能使用一次，所以限制使用的王牌数为 ，每种牌不够 张需要王牌补，计算使用的王牌数为判断是否满足条件即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, a[105];

bool check(ll x) {
  ll cnt = min(m, x);
  for (ll i = 1; i <= n; i++) cnt -= max(x - a[i], 0LL);
  return cnt >= 0;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  ll l = 0, r = 1e9, mid;
  while (l + 1 < r) {
    mid = l + r >> 1;
    if (check(mid))
      l = mid;
    else
      r = mid;
  }
  cout << l << '\n';
  return 0;
}