POJ 3273 Monthly Expense 【二分答案】

题意：给出n天的花费，需要将这n天的花费分成m组，使得每份的和尽量小，求出这个最小的和

看题目看了好久不懂题意，最后还是看了题解

二分答案，上界为这n天花费的总和，下界为这n天里面花费最多的那一天

如果mid>=m,说明mid偏小，l=mid+1,

如果mid<m,说明mid偏大，r=mid,

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=1000005;
17 
18 int a[maxn];
19 int n,m,k;
20 
21 int ok(int v){
22     int ans=0;
23     int cnt=0;
24     for(int i=1;i<=n;i++){
25         ans+=a[i];
26         if(ans>v){
27             ans=a[i];
28             cnt++;
29         }
30     }
31     if(cnt>=m) return 0;
32     return 1;
33 }
34 
35 int main(){
36     while(scanf("%d %d",&n,&m)!=EOF){
37         int minn=-1,maxx=0;
38         for(int i=1;i<=n;i++) {
39             scanf("%d",&a[i]);
40             maxx+=a[i];
41             minn=max(minn,a[i]);        
42         }
43         
44         LL l=minn,r=maxx,mid;
45         while(l<r){
46             mid=(l+r)/2;
47             if(ok(mid)) r=mid;
48             else l=mid+1;        
49         //    printf("l=%d
",l);
50         //    printf("r=%d
",r);
51         //    printf("mid=%d
",mid);
52         }
53         
54     printf("%I64d
",l);
55     }
56     return 0;
57 }

View Code