[백준 2805] 나무 자르기

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v;
int M;

long long getsum(long long mid) {
	long long sum = 0;
	auto it = lower_bound(v.begin(), v.end(), mid); // O(logN) < O(N)

	for (it; it != v.end(); it++) sum += (*it) - mid;
	return sum;
}

// 적어도 M미터 == 정확히 M미터거나 M미터보다 크게 가져간다
long long binary_search(int start, int end) {
	long long  mid;
	long long sum;
	long long ans;

	while (start <= end) {
		mid = (start + end) / 2;
		sum = getsum(mid);

		// M보다 크면 더 잘라야함
		if (sum > M) { start = mid + 1; ans = mid; }
		// M보다 작으면 덜 잘라야함
		else if (sum < M) { end = mid - 1; }
		// 같을때는 오직 한군데 -> 찾자마자 break
		else { ans = mid; break; }
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, x; cin >> N >> M;

	for (int i = 0; i < N; i++) { cin >> x; v.push_back(x); }

	sort(v.begin(), v.end());
	cout << binary_search(0, v.back());
	return 0;
}