[2805] 나무 자르기

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

2805번: 나무 자르기

<문제>

절단기를 mid으로 설정했을 때 얻을 수 있는 나무의 길이를 리턴하는 함수를 구현했다면,

나무가 M보다 더 작게 잘렸다면 절단기의 높이를 낮추고, 반대로 리턴값이 M이상일 때에는

이를 정답으로 기록해두고, 절단기의 높이를 높인다.

초기 범위는 나무의 높이와도 같이 (0, 10억)으로 설정해주면 되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, ans;
vector<ll> v;
ll f(ll mid) {
    ll i, ret = 0;
    for (i = 0; i < n; i++) ret += max(0LL, v[i] - mid);
    return ret;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    ll i;
    for (i = 0; i < n; i++) {
        ll x;
        cin >> x;
        v.push_back(x);
    }
    ll s = 0, e = 1000000000;
    while (s <= e) {
        ll mid = (s + e) / 2;
        ll ret = f(mid);
        if (ret >= m) {
            ans = max(mid, ans);
            s = mid + 1;
        } else
            e = mid - 1;
    }
    cout << ans;
    return 0;
}