나무 자르기 2805

문제

접근 방법

랜선 자르기와 동일한 원리이다.
판단기준이 다를 뿐이다. 랜선 자르기는 나누기였다면 나무 자르기는 빼기이다.

코드

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M, ret = 0;
    ll low = 0, high = 0, mid;
    cin >> N >> M;
    vector<int> trees(N);
    for (int i = 0; i < N; ++i)
    {
        int tree;
        cin >> tree;
        trees.push_back(tree);
        if (high < tree)
            high = tree;
    }
    while (low <= high)
    {
        ll sum = 0;
        mid = (low + high) / 2;
        for (int tree : trees)
        {
            sum += ((tree - mid) > 0 ? (tree - mid) : 0);
        }
        if (sum >= M)
        {
            low = mid + 1;
            if (ret < mid)
                ret = mid;
        }
        else
        {
            high = mid - 1;
        }
    }
    cout << ret;
    return 0;
}

풀이

int 범위를 넘어가는 것, 적어도 M 미터 높이의 나무를 원하는 것, 합계에 음수값이 들어가면 안 되는 것을 유의하면 된다.