나무 자르기 (feat. 백준, 2805번)

나무 자르기
https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M, arr[1000000];
	long long start = 1, end = 0, mid, tmp, ans = 0;
	cin >> N >> M;
	for (register int n = 0; n < N; ++n)
		cin >> arr[n], end = max(end, (long long)arr[n]);
	while ((end - start) >= 0) {
		tmp = 0;
		mid = (end + start) / 2;
		for (register int n = 0; n < N; ++n)
			if (((long long)arr[n] - mid) > 0)
				tmp += (long long)arr[n] - mid;
		if (tmp >= M) {
			start = mid + 1;
			ans = max(ans, mid);
		}
		else
			end = mid - 1;
	}
	cout << ans;
	return 0;
}
// *&)*@*

앞선 '랜선 자르기' 문제와 동일한 형태입니다. 먼저 풀어보시길 권장합니다.

랜선 자르기 (feat. 백준, 1654번)