[c++][BOJ][2805] 나무 자르기

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

2805번: 나무 자르기

바로 이전 문제와 같은 유형의 문제입니다.

 

최대 길이와 0 사이에서 이분탐색을 해서 나무를 최대한 적게 자르는 높이를 구하는 문제입니다.

#include <iostream>
using namespace std;

long long int arr[1000000];

int main(){
    long long int n, k;
    cin >> n >> k;
    
    long long int maxLen = 0;
    long long count = 0;
    
    for(int i=0; i<n; i++){
        cin >> arr[i];
        maxLen = max(maxLen , arr[i]);
    }
    
    long long int start = 0, end = maxLen, mid;
    
    while(start <= end){
        mid = (start + end) / 2;
        
        long long int part = 0;
        long long int minus;
        
        for(int i=0; i<n; i++){
            minus = arr[i] - mid;
            
            if(minus > 0){
                part += minus;
            }
        }
        
        if(part >= k){
            start = mid + 1;
            count = max(count, mid);
        }
        else {
            end = mid - 1;
        }
    }
    
    cout << count;
}