백준 2805 나무자르기

/*
1. 나무의 수 n과 필요한 길이 m을 입력받는다.
2. 나무의 길이를 m번 반복하며 입력받는다.
3. 이분 탐색을 위해 나무의 길이를 정렬한다. 
4. 자를 수 있을 때까지 반복한다.(low 값이 high보다 작거나 같을 때까지만)
4-1. 자를 지점 cut = low + high /2
4-2. 각각의 나무의 길이에서 cut 만큼 빼고, 남은 길이를 sum 변수에 저장한다.
4-3. sum 값이 필요한 길이 m 보다 길다면 환경을 위해 cut을 더 올려야한다. 즉, low = cut + 1 이다.
4-4. sum 값이 필요 길이 m보다 짧다면 cut을 더 내려야한다. 즉, high = cut - 1 이다.
5. 위의 과정을 반복하며 최대 cut 높이를 구하자.

주의사항: 
1. 선형 탐색을 할 경우.. 나무의 수가 너무 많으니까 시간초과가 날 수 있다. 그러므로 이분 탐색을 사용한다.
2. 나무의 총 길이가 매우 길어질 수 있기 때문에.. sum은 long long 자료형을 사용하자.
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
// 최대 cut 높이를 찾아서 반환하는 binary_search
int binary_search(int low, int high, int target)
{
	int max = 0;
	while (low <= high)
	{
		long long sum = 0;
		int cut = (low + high) / 2;

		for (auto tree : v)
		{
			if (tree > cut) sum += tree - cut;
		}
		
		if (sum >= target)
		{
			max = cut;
			low = cut + 1;
		}
		else high = cut - 1;
	}
	return max;
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int treeh;
		cin >> treeh;
		v.push_back(treeh);
	}
	sort(v.begin(), v.end());

	cout << binary_search(0, v.back(), m);
}