[C++] 백준 2805번 나무 자르기

이분탐색으로 문제를 풀었습니다.

M미터의 나무를 가져가기 위해서 전체 나무들이 X가 되게 자를 때
X갖 가장 큰 경우의 값을 출력하는 문제입니다.

left와 right를 설정해준 다음 가운데 값을 비교하면서
이분탐색을 해주어서 문제를 해결하였습니다.

 

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

typedef long long ll;

int n, m;
int result = 0;
ll sum = 9876543210;
ll leftN, rightN;
ll arr[1000001];

void binary_find(ll x)
{
	ll temp = 0;

	if (leftN > rightN) {
		return;
	}

	for (int i = 0; i < n; ++i) {
		if (arr[i] > x) {
			temp += arr[i] - x;
		}
	}

	if (m > temp) {
		rightN = x - 1;
		binary_find((rightN + leftN) / 2);
		return;
	}
	else {
		if (sum >= temp) {
			sum = temp;
			result = x;
		}
	}

	leftN = x + 1;
	binary_find((rightN + leftN) / 2);
}

int main(int argc, char *argv[]) 
{
	scanf("%d", &n);
	scanf("%d", &m);

	memset(arr, 0, sizeof(arr));

	for (int i = 0; i < n; ++i) {
		scanf("%lld", &arr[i]);
	}
	sort(arr, arr + n);

	leftN = 0;
	rightN = arr[n - 1];

	binary_find((leftN + rightN) / 2);

	printf("%d\n", result);

	return 0;
}