2805번: 나무 자르기 - 이분 탐색(매개 변수 탐색)

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

2805번: 나무 자르기

1654번 랜선 자르기와 동일한 문제.

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

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

ll N, M;
vector<ll> tree;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;
    for (int i{1}; i <= N; i++)
    {
        ll len;
        cin >> len;
        tree.push_back(len);
    }

    ll l = 0, r = 1000000000;
    while (l < r)
    {
        ll m = (l + r) / 2 + 1;

        ll sum = 0;
        for (ll len : tree)
        {
            if (m >= len)
                continue;
            sum += len - m;
        }

        if (sum >= M)
            l = m;
        else
            r = m - 1;
    }
    cout << l << "\n";
}