POJ.3273 Monthly Expense

1.Problem
http://poj.org/problem?id=3273

2.Idea
Binary Search

3.Source

 int N, M;  
 int x[100005];  
 bool C(int d)  
 {  
      int cnt = 0;  
      int sum = 0;  
      for (int i = 0; i < N; i++) {  
           if (x[i] > d) return false;  
           else if(sum + x[i] > d){  
                cnt++;  
                sum = x[i];  
           }  
           else {  
                sum += x[i];  
           }  
      }  
      if (cnt < M) return true;  
      else return false;  
 }  
 void solve()  
 {  
      ll lb = 0, ub = 12345678900;  
      while (ub - lb > 1) {  
           int mid = (lb + ub) / 2;  
           if (C(mid)) ub = mid;  
           else lb = mid;  
      }  
      printf("%d\n", ub);  
 }  
 int main()  
 {  
      cin >> N >> M;  
      for (int i = 0; i < N; i++) cin >> x[i];  
      solve();  
      return 0;  
 }