POJ(PKU) 3723 Monthly Expense

二分探索で最小値を求める。

#include <cstdio>

using namespace std;
const int INF = 100002;
int n,m,d[1000002];

bool ch(int x){
  int u = 1;
  int sum = 0;
  for(int i = 0;i < n;i++){
    if(d[i] > x)return false;
    if(d[i] + sum > x){
      u++;
      sum = d[i];
    }else{
      sum += d[i];
    }
  }
  
  if(u <= m) return true;
  else return false;
}


int main(){
  

  scanf("%d%d",&n,&m);
  
  for(int i = 0;i < n;i++){
    scanf("%d",&d[i]);
  }
  
  int lb = 0,ub = INF;
  
  while(ub - lb > 1){
    int mid = (ub + lb) / 2;
    if(ch(mid)) ub = mid;
    else lb = mid;
  }

  printf("%d\n",ub);
  
  return 0;
  
}