poj 3273 Monthly Expense(贪心+二分)

题意：把n个数分成m份，使每份的和尽量小，输出最大的那一个的和。

思路：二分枚举最大的和，时间复杂度为O(nlog(sum-max));

一道很好的题。

 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
", high);
44     }
45     return 0;
46 }

以后还是用这种形式的二分吧

while(left<right)

{

if()

left=mid+1;

else right=mid;

}

代码：

 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++;
35                     w = a[i];
36                 }
37             }
38             if(cou <= m)
39             high = mid;
40             else
41             low = mid+1;
42         }
43         printf("%d
", low);
44     }
45     return 0;
46 }