poj 3273 Monthly Expense（二分穷举）

题目：http://poj.org/problem?id=3273

题意：把n天分为m组，每组的天数是连续的，求每组花费之和最小

二分穷举，把花费的最大值和最小值求出，对其进行二分，从而求出符合要求的最小花费

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int a[100010];
 5 int n,m;
 6 int juge(int mid)
 7 {
 8     int sum=0;
 9     int num=1;
10     int i;
11     for(i=0;i<n;i++)
12     {
13         if(sum+a[i]<=mid)
14         sum+=a[i];
15         else
16         {
17             sum=a[i];
18             num++;
19             if(num>m)
20             return 0;
21         }
22     }
23     return 1;
24 }
25 int main()
26 {
27     scanf("%d %d",&n,&m);
28     int i;
29     int low=0;
30     int high=0;
31     for(i=0;i<n;i++)
32     {
33         scanf("%d",&a[i]);
34         high+=a[i];
35         if(a[i]>low)
36         low=a[i];
37     }
38     int mid;
39 
40     while(low<high)
41     {
42         mid=(low+high)/2;
43         if(juge(mid))//如果mid可以将n分成m组，证明所求值在low到mid之间
44         high=mid-1;
45         else
46         low=mid+1;
47 
48     }
49     mid=(low+high)/2;
50     cout<<mid<<endl;
51     return 0;
52 }