poj3273 Monthly Expense

题意：

Monthly Expense
FJ是一个令人震惊的会算账的人才，他意识到他可能要耗尽他的钱来运行经营农场了。他已经计算并且记录了他将来N天中每一天的花费。
FJ想要搞一个预算，一个连续的集合M段时间，叫做fajomonths，每一段包含一天或者更多连续的天数。

fajomonths的话费是一样的
FJ的目标是找到fajomonths花费最小值。

二分求解，left=0 right=所有天数花费之和。

还有一个细节，就是，要找到所有天数最大的值，然后在每次二分时候做一次特殊处理，因为很有可能mid值小于该最大值。。。

 1 #include <stdio.h>
 2 int days[100000+10];
 3 int n,m;
 4 int find(int mmax,int sign){
 5     int left=0;
 6     int right=mmax;
 7     int mid;
 8     int cnt;
 9     int leave;
10     int tmp;
11     int res=mmax;
12     int i;
13     while(right>=left){
14         cnt=0;
15         mid=(left+right)/2;
16         tmp=mid;
17         cnt++;
18         for(i=0;i<n;){
19             if(mid<days[i]){
20                 cnt=m*2;
21                 break;
22             }
23             if(tmp>=days[i])
24                 tmp=tmp-days[i],++i;
25             else{
26                 tmp=mid;
27                 cnt++;
28             }
29 //            printf("tmp=%d
",tmp);
30         }
31         if(cnt>m){
32             left=mid+1;
33         }else{
34             right=mid-1;
35             if(mid<res)
36                 res=mid;
37         }
38 //        printf("l=%d,r=%d,mid=%d
",left,right,mid);
39         //printf("cnt=%d
",cnt);
40         if(mid==right&&right==left) break;
41     }
42     return res;
43 }
44 int main(){
45     int i;
46     int tot;
47     int mmax;
48     while(~scanf("%d%d",&n,&m)){
49         tot=0;
50         mmax=0;
51         for(i=0;i<n;++i){
52             scanf("%d",&days[i]);
53             tot+=days[i];
54             if(days[i]>mmax) mmax=days[i];
55         }
56         printf("%d
",find(tot,mmax));
57     }
58     return 0;
59 }