POJ 3273 Monthly Expense 二分枚举

二分枚举，据说是经典题，看了题解才做的，暂时还没有完全理解。。

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int n, m;
 5 int a[100000];
 6 
 7 bool judge(int x)
 8 {
 9     int money = 0, cnt = 1;
10     for(int i = 0; i < n; i++)
11     {
12         if(money + a[i] <= x)
13             money += a[i];
14         else
15         {
16             money = a[i];
17             cnt++;
18         }
19     }
20     if(cnt > m)
21         return 0;
22     else return 1;
23 }
24 
25 int main()
26 {
27     int low = 0, high = 0;
28     scanf("%d %d", &n, &m);
29     for(int i = 0; i < n; i++)
30     {
31         scanf("%d", &a[i]);
32         if(low < a[i])
33             low = a[i];
34         high += a[i];
35     }
36     int mid = (low + high) / 2;
37     while(low < high)
38     {
39         if(judge(mid))
40             high = mid - 1;
41         else low = mid + 1;
42         mid = (low + high) / 2;
43     }
44     printf("%d
", mid);
45     return 0;
46 }

View Code