[백준-2805] 나무자르기

2805번: 나무 자르기

간단한 이분탐색 문제이다.

최대값을 right로 0을 left 로 설정한 후 calc 함수만 짠뒤 간단히 이분탐색을 돌리면 풀리는 간단한 문제이다.

다만 값의 범위가 int 값의 범위를 넘어가기 때문에 이를 long long 으로 변환해주어 적절하게 풀면 간단히 풀린다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>


using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, string> tii;
typedef long long LL;

LL n, m;
LL arr[1000001];

LL calc(LL x) {
    LL res = 0;
    for (int i = 0; i < n; i++) {
        res += (arr[i] - x > 0) ? arr[i] - x : 0;
    }
    return res;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    LL right = 1000000000;
    LL left= 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    LL mid;
    LL ans = 0;
    while (left <= right) {
        mid = (left + right) / 2;
        LL res = calc(mid);
        if (res >= m) {
            ans = max(ans, mid);
            left = mid + 1;
        }
        else if(res < m){
            right = mid - 1;
        }
    }

    cout << ans;

    return 0;
}