백준 2805번:나무 자르기

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

2805번: 나무 자르기

 

 이 문제는 이분 탐색으로 푸는 것이다. 일단 톱날의 높이가 낮아지면 가져가는 나무의 길이는 증가하고 

톱날의 높이가 높아지면 가져가는 나무의 길이는 줄어든다. 그리고 우리는 가져가는 나무의 길이의 총량이 중요하므로

톱날로 잘랐을때 나오는 나무랑 가져가야하는 나무의 길이를 비교하면서 이분 탐색을 실시하면 된다.

코드를 보자

#include <iostream>
#include <vector>
using namespace std;
int n,m;
bool check(vector<long long>& v,int x){        //잘려진 나무의 총 길이와 가져가야하는 나무의 길이 비교
    long long cnt=0;
    for(int i=0;i<n;i++){
        long long temp= v[i]-x;
        if(temp>=0){
            cnt+=temp;
        }
    }
    return cnt>=m;
}
int main(){
    cin >>n>>m;
    vector<long long> v(n);
    long long max=0;
    for(int i=0;i<n;i++){
        cin >>v[i];
        if(max<v[i]){
            max=v[i];
        }
    }
    long long left=0;
    long long right=max;
    long long ans=0;
    while(left<=right){     //가장 큰 길이를 가진 나무까지만 톱날을 자르는게 의미가 있으므로 right는 가장 큰
        long long mid=(left+right)/2;
        int ok=check(v,mid);
        if(ok){
            left=mid+1;
            if(ans<mid){          //높이 최대값을 구해야하므로 
                ans=mid;
            }
        }
        else{
            right=mid-1;
        }
    }
    cout << ans;

}