poj 3273 Monthly Expense(贪心+二分)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 100000+10;
 8 int a[maxn];
 9 
10 int main()
11 {
12     int n, m, i, Max, sum;
13     while(~scanf("%d%d", &n, &m))
14     {
15         Max = -1;
16         sum = 0;
17         for(i = 0; i < n; i++)
18         {
19             scanf("%d", &a[i]);
20             sum += a[i];
21             if(Max < a[i])
22             Max = a[i];
23         }
24         int high = sum, low = Max, mid;
25         while(high>low)
26         {
27             mid = (high+low)/2;
28             int cou = 1, w = 0;
29             for(i = 0; i < n; i++)
30             {
31                 w += a[i];
32                 if(w>mid)
33                 {
34                     cou++;  //cou记录最大值为mid的情况下，可以分成几份
35                     w = a[i];
36                 }
37             }
38             if(cou>m)
39             low = mid+1;
40             else
41             high = mid-1;
42         }
43         printf("%d\n", high);
44     }
45     return 0;
46 }