二分

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

你有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，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。

输入描述:

第一行包含两个整数n, m，即牌的种数和joker的个数。
第二行包含n个整数ci，即每种牌的张数。

输出描述:

输出仅一个整数，即最多组成的套牌数目。
示例1

输入

复制 
3 4
1 2 3

输出

复制 
3

说明

样例解释
输入数据表明：一共有1个1，2个2，3个3，4个joker。最多可以组成三副套牌：{1,J,3}, {J,2,3}, {J,2,3}，joker还剩一个，其余牌全部用完。

备注:

数据范围
50%的数据满足：2 < = n < = 5, 0 < = m < = 10^ 6, 0< = ci < = 200
100%的数据满足：2< = n < = 50, 0 < = m, ci <= 500,000,000。

解题思路

答案要求最大，那么如果我们假设使用ans个方案时答案合理，那么我们就要去尝试大于ans的部分，其余就是小于。
那么很明显的二分思路了。
如果当前个数小于mid的时候，说明就要用大王去填坑，最后判断够不够的大王即可。

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 50 + 7;
int a[N];

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)    a[i] = read();
    int l = 0, r = 1e9, mid, ans;
    while (l <= r) {
        mid = r + l >> 1;
        ll cnt = 0;
        for (int i = 1; i <= n; ++i)
            if (a[i] < mid)    cnt += mid - a[i];
        if (cnt > mid or cnt > m)    r = mid - 1;
        else ans = mid,l = mid + 1;
    }
    write(ans);
    return 0;
}