题目连接：

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

题面：

你有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，即每种牌的张数。
输出：
输出仅一个整数，即最多组成的套牌数目。

input:
3 4
1 2 3

output:
3

说明：
链接：https://ac.nowcoder.com/acm/problem/19916
来源：牛客网

样例解释
输入数据表明：一共有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。

分析：

观察数据范围可得，最多可以组成 10810^8 数量级的牌数。
想到使用二分枚举答案+检验来确认结果，若当前提供的可以组成x组牌，那必然可以组成0 ~ x组牌，满足答案的连续/线性性质：

  • 在二分枚举值为mid的情况下，对每种牌的牌数不满mid时，用joker牌补；

  • 统计在当前假定能组成的总牌数为mid的情况下需要补充的joker牌数；

  • 若当前需要补充的joker牌数大于当前假定能组成的总牌数mid，（基于鸽笼/抽屉原理）说明一定至少有一组牌中有两个joker牌，不满足要求，return false;

  • 若当前需要补充的joker牌数大于所能提供的joker牌数m，则不满足要求，return false;

  • 其他情况，都满足要求，return true;

代码：

#include<iostream>
#include<math.h>
#include<algorithm>

using namespace std;
typedef long long ll;

int n, m;
int c[55] = {};


bool check (int mid) {
	
	ll cnt_j = 0;
	for (int i = 0; i < n; i++) {
		if (c[i] < mid) {
			cnt_j += mid - c[i];	
		}
	}
	if (cnt_j <= m && cnt_j <= mid) {
		return true;
	}
	else {
		return false;
	}
	
}


int main () {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}	

	int l = 0, r = 1e9;
	
	while (l <= r) {
		int mid = l + r >> 1;
		
		if (check(mid)) {
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}	
	
	cout << r << endl;

}