poj3273Monthly Expense

View Code
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<stdlib.h>
 5 #include<cmath>
 6 using namespace std;
 7 int num[100010],n,m;
 8 int judge(int mid)
 9 {
10     int i,s=0,k=1;
11     for(i = 1 ; i <= n ; i++)
12     {
13         s+=num[i];
14         if(s>mid)
15         {
16             s = num[i];
17             k++;
18         }
19     }
20     if(k>m)
21        return 1;
22     else
23        return 0;
24 }
25 int main()
26 {
27     int i,j;
28     while(cin>>n>>m)
29     {
30         int high=0,low=0;
31         for(i = 1; i <= n ;i++)
32         {
33                 cin>>num[i];
34                 high+=num[i];
35                 if(num[i]>low)
36                     low = num[i];
37         }
38         int mid = (low+high)/2;
39         while(low<high)
40         {
41             if(judge(mid))
42             low = mid+1;
43             else
44             high = mid-1;
45             mid = (low+high)/2;
46         }
47         cout<<mid<<endl;
48     }
49     return 0;
50 }