(2805) 나무 자르기

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

단계별로 풀어보기

25단계(이분 탐색) 4번째

 

 

 

전기톱 높이를 x로 설정했을 때 얻어지는 나무의 길이가 M보다 큰지 작은지에 대한 결정 문제로 바꾸고 이분 탐색을 수행하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector<int> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  int lo= 0, hi= 1000000001;
  
  while(lo+1<hi){
    int mid= (lo+hi)/2;
    long cnt= 0;
    
    for(int i=0;i<n;i++)  cnt+= max(0, v[i]-mid);
    
    (cnt>=m ? lo : hi)= mid;
  }
  
  cout << lo;
  
  return 0;
}