[每日一题] [NC19916] 扑克牌

题目大意：有n种扑克牌，每种有ci个。还有m张百搭牌。一个套牌是1,2,...,n或者用百搭牌代替其中任一张。最多可以造出几个套牌。

https://ac.nowcoder.com/acm/problem/19916

也许有纯数学的做法，但是能造出k个套牌显然也能造出k-1个套牌，所以feasibility符合单调性。可以使用binary search寻找最大的k，使得可以造出k个套牌。

对于k个套牌，第i中套牌必须使用max(0, k-ci)个百搭牌，而且每个百搭牌只能在一套里出现，所以总和不超过min(m, k)。

bool feas(ll cnt, VL& c, ll m) {
  // Checks if it's possible to get cnt decks.
  VL each;
  FORE(x, c) {
    each.PB(max(0LL, cnt - x));
  }
  ll sm = SUM(each);
  return sm <= m && sm <= cnt;
}

int main(int argc, char* argv[]) {
  /* Do not use for codejam. */
  /* ios_base::sync_with_stdio(false); cin.tie(NULL); */
  readint(n);readlong(m);
  readvl(c, n);
  ll lo = 0, hi = 20000000000LL;
  while (lo < hi) {
    ll mi = RMID(lo, hi);
    if (feas(mi, c, m)) {
      lo = mi;
    } else {
      hi = mi - 1;
    }
  }
  printlong(lo);
  return 0;
}