907:Winterim Backpacking Trip

問題文
http://uva.onlinejudge.org/external/9/907.html

n個の休憩地点がある山をk回の休憩をして登る。
一回あたりの登る距離の最悪の長さを最小化せよ。

解を決め打ちして二分探索した。
動的計画法でも解けるらしい。

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int n,k;
vector<int>v;
 
bool C(int x){
  int K=0,tmp=0;
  for(int i=0;i<v.size();i++){
    if(x<v[i])return false;
    if(tmp+v[i]<=x)tmp+=v[i];
    else K++,tmp=v[i];
  }
  return K<=k;
}
 
int main(void){
 
  while(cin >> n >> k){
    v.clear();
    v.resize(n+1);
 
    for(int i=0;i<n+1;i++)cin >> v[i];
 
    int l=0,r=100,mid;
     
    while(r-l>1){
      mid=(l+r)/2;
      if(C(mid))r=mid;
      else l=mid;
    }
    cout << r << endl;
  }
 
  return 0;
}