Description

你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。

Solution

求最大的答案，首先考虑推公式，公式不好推，转而考虑二分答案然后去 。 我们二分一个答案，然后对于每一种牌去检验，如果当前的牌小于答案，那么就要用 去填充，最后注意我们二分的答案不能超过我们用的 数，否则就会出现一次用了两张 的情况，是不合法的。
PS: 我二分的上界一开始是 1e18, 把自己 哭了

Code

#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int mod = 100000000;
const int N = 5e5 + 5;
typedef long long ll;
const double pi = acos(-1.0);
int a[N];
int n, m;
bool check(int x) {
  ll cur = 0;
  for(int i = 1; i <= n; i++) {
    if(a[i] < x) {
      cur += x - a[i];
    }
  }
  return cur <= m && cur <= x;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> a[i];
  int left = 0, right = 1e9, ans = 0;
  while(left <= right) {
    int mid = left + right >> 1;
    if(check(mid)) {
      left = mid + 1;
      ans = mid;
    } else {
      right = mid - 1;
    }
  }
  cout << ans << "\n";
  return 0; 
}