[백준/C++] 2805번: 나무 자르기 (이분탐색)

long long 자료형을 안쓰면 틀린다.

 

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


const int MAX = 1000000;



int N;
long long M; //나무 수, 나무 길이
long long tree[MAX];


bool condition(long long height) { // 앞부분에 존재하는지판단

	long long sum = 0;

	for (int i = 0; i < N; i++) {

		if (tree[i] > height)
			sum += tree[i] - height;
	}

	if (sum >= M)
		return true;

	return false;

}


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;


	long long low = 1;
	long long high = 0;


	for (int i = 0; i < N; i++) {
		cin >> tree[i];
	}

	high = *max_element(tree, tree + N);

	long long  ans = 0;
	while (low <= high) {

		long long mid = (low + high) / 2;

		if (condition(mid)) {

			ans = mid;
			low = mid + 1; //0~mid사이에 존재->더 큰수 찾아볼까?

		}
		else {

			high = mid - 1;

		}
	}

	cout << ans << '\n';
	return 0;
}