2805_나무 자르기

이진 탐색 : 요소들이 정렬되어 있을 때 사용
-> 제일 큰 나무의 높이를 가지고 탐색

#include <iostream> 
#include <vector>

using namespace std;

int main() {
	long long n, m;
	cin >> n >> m;
	vector<long long> tree;
	long long left = 0;
	long long right = 0;
	long long res=0;
	for (int i = 0; i < n; i++) {
		long long x;
		cin>>x;
		right = max(x, right);
		tree.push_back(x);
	}
	
	while (left<=right) {
		long long sum=0;
		int mid = (left + right) / 2;
		for (int i = 0; i < n; i++) {
			if (tree[i] > mid) {
				sum += tree[i] - mid;
			}
		}
		if (sum >= m) {
			if (res<mid) {
				res = mid;
			}
			left = mid + 1;
		}
		else if(sum == m) {
			res = mid;
			break;
		}
		else {
			right = mid - 1;
		}
	}
	cout<<res;
}