[백준 2805] 나무 자르기

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

요구사항

1. 적어도 원하는 나무 길이를 가져가기 위한 최소 나무 길이

 

풀이

1.  이분 탐색으로 찾기

적어도 m만큼만 가져갈 수 있다면 정답 가능성이 있는거임

정확히 m을 가져가는것이 아님

 

 

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

typedef long long ll;

ll n, m;
ll map[1000001];
ll tans = 0;
ll maxv = 0;
ll minv = 0;
bool check(ll k) {
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (map[i] - k > 0) {
			ans += (map[i] - k);
		}
		if (ans >= m)
			return true;
	}
	if (ans >= m)
	{
		return true;
	}
	else {
		return false;
	}
}
ll Find() {
	ll left = minv;
	ll right = maxv;
	ll mid = 0;
	int cnt = 0;
	//cout << "M" << maxv << " minv" << minv << endl;
	while (left <= right) {
		mid = (left + right) / 2;
		if (check(mid)) {
			left = mid + 1;
			tans = max(tans, mid);
		}
		else {
			right = mid - 1;
		}
	}
	return tans;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		scanf("%lld", &map[i]);
		if (maxv < map[i])
			maxv = map[i];
	}
	cout << Find() << endl;




}