[PS] 백준 2805번: 나무 자르기

|

문제

내가 이해한 문제 내용

나무를 최대한 적게 자르면서 적어도 $M$미터의 나무를 가져가도록 설정할 수 있는 높이의 최댓값을 구하여라.

접근 방식

이분탐색을 계속 풀었더니 이제 보이기 시작한다.

어려웠던 점 & 배운 점

딱히 없었다.

시간복잡도

$O(NlgM)$

코드

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

typedef long long ll;

ll n,m,_min,_max;
ll tree[1000005];

int main(void)
{
    _min = 2e8, _max = 0;
    scanf("%lld%lld",&n,&m);
    for(int i=0; i<n; i++) {
        scanf("%lld",&tree[i]);
        _min = min(_min,tree[i]);
        _max = max(_max,tree[i]);
    }

    ll l=_min, r=_max;
    ll ans = 0;

    while(l<=r){
        ll mid = (l+r)/2;
        ll meter = 0;
        for(int i=0; i<n; i++){
            meter += (tree[i]>mid ? tree[i]-mid : 0);
        }
        if(meter<m) r = mid-1;
        else {
            ans = mid;
            l = mid+1;
        }
    }
    printf("%lld",ans);
    return 0;
}