Binary Search 2805

1
//2805  파라메트릭 서치
2
//나무 자르기 - 절단기의 높이 설정    h를 올리면 남은 길이가 줄어듬 그래서 문제는 [정해진 남은길이 이상, h의 높이구하기]
3
#include <bits/stdc++.h>
4
#define fIO ios_base::sync_with_stdio(false); \
5
cin.tie(NULL);
6
using namespace std;
7

8
int n;
9
long long m;
10
vector<int> tree;
11

12
bool is_possible(int h)
13
{
14
    long long sum = 0;
15
    for(int i = 0; i < n; i++)
16
    {
17
        if(tree[i] > h)
18
            sum += (tree[i]- h);
19
    }
20
    return sum >= m;
21
}
22
int main(void)
23
{
24
    fIO
25
    cin >> n >> m;
26
    tree.resize(n);
27
    for(int i = 0; i < n; i++)
28
    {
29
        cin >> tree[i];
30
    }
31

32
    int left = 0, right = *max_element(tree.begin(), tree.end());
33
    int answer = 0;
34

35
    while(left <= right)
36
    {
37
        int mid = (left + right) / 2;
38
        if(is_possible(mid))
39
        {
40
            answer = mid;
41
            left = mid + 1;
42
        }
43
        else
44
        {
45
            right = mid - 1;
46
        }
47
    }
48

49
    cout << answer << "\n";
50

51
}