502 二分答案

// 502 二分答案.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
http://oj.daimayuan.top/course/22/problem/61



给一个序列 a1,a2,…,an。

你可以对这个序列进行操作，每次操作可以选择一个元素，把它加 1
，经过不超过 k次操作之后，希望序列里面的最小值最大。问这个值是多少。

输入格式
第一行两个整数 n,k
。接下来一行 n个整数，表示 a1,a2,…,an。

输出格式
输出一行，一个整数，表示答案。

样例输入1
5 10
1 4 2 6 8
样例输出1
5
样例输入2
1 10000000000000
100000000
样例输出2
10000100000000
数据规模
对于 100%的数据，满足 1≤n≤105,1≤ai≤108,0≤k≤1013
*/


#include <iostream>



using namespace std;

const int N = 100010;
long long a[N];
long long n, k;


bool check(long long mid) {
	long long cnt = 0;
	for (int i = 0; i < n; i++) {
		if(a[i]<=mid)
			cnt += mid - a[i];
	}

	return cnt <= k;
}

int main()
{
	cin >> n >> k;

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

	long long l = 0; long long r = 10000100000010;
	while (l < r) {
		long long mid = (l + r + 1) >> 1;
		if (check(mid)) l = mid; 
		else r = mid - 1;
	}

	
	
	cout << l << endl;

	return 0;
}