bzoj1639 / P2884 [USACO07MAR]每月的费用Monthly Expense

二分经典题

二分每个段的限制花费，顺便统计下最大段

注意可以分空段

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int max(int &a,int &b){return a>b?a:b;}
 6 #define N 100001
 7 int a[N],n,m,ans=2e9;
 8 bool check(int lim){
 9     int st=0,tot=0,mxd=0;
10     for(int i=1;i<=n;++i){
11         if(a[i]>lim) return 0;
12         if(tot+a[i]>lim)
13             ++st,mxd=max(mxd,tot),tot=0;
14         tot+=a[i];
15     }++st;
16     mxd=max(mxd,tot);
17     if(st<=m) ans=min(ans,mxd);//顺便统计最大段的最小花费
18     return st<=m;
19 }
20 int main(){
21     scanf("%d%d",&n,&m);
22     for(int i=1;i<=n;++i) scanf("%d",&a[i]);
23     int l=0,r=1e9+1;//二分限制花费
24     while(l<r){
25         int mid=l+(r-l)/2;
26         if(check(mid)) r=mid;
27         else l=mid+1;
28     }printf("%d",ans);
29     return 0;
30 }

View Code