砍树

落谷 P1873
一个二分查找

#include<iostream>
using namespace std;
#include<algorithm>
#include<cmath>
typedef long long ll;
ll n;
ll m;
ll a[1000005];
ll ans = 0;
int main()
{
	cin >> n >> m;
	for (ll i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	ll max_ = a[n - 1];
	//cout << max_ << endl;
	ll l = a[0];
	ll r = max_;
	ll mid = (r + l) / 2;
	while (l <= r)
	{
		ans = 0;
		for (ll i = 0; i < n; i++)
		{
			if (mid < a[i])
			{
				ans = ans + a[i] - mid;
			}
		}
		//cout << "mid:" << mid << "ans:" << ans << endl;
		if (ans == m)
		{
			break;
		}
		if (ans < m)
		{
			r = mid - 1;
			mid = (r + l) / 2;
		}
		if (ans > m)
		{
			l = mid + 1;
			mid = (r + l) / 2;
		}
	}
	cout << mid;
	return 0;
}