洛谷 167. [USACO Mar07] 月度花费

167. [USACO Mar07] 月度花费

二分答案

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define maxn 1000000
 4 int n,m,minn,maxx;
 5 int a[maxn];
 6 
 7 bool check(int x)
 8 {
 9     int ans=1,bns=0;
10     for(int i=1;i<=n;i++)
11     {
12         if(bns+a[i]>x) bns=a[i],ans++;
13         else bns+=a[i];
14     }
15     if(ans<=m) return true;
16     else return false;
17 }
18 
19 int main()
20 {
21     freopen("expense.in","r",stdin);
22     freopen("expense.out","w",stdout);
23     scanf("%d%d",&n,&m);
24     for(int i=1;i<=n;i++)
25     {
26         scanf("%d",&a[i]);
27         minn=max(minn,a[i]);
28         maxx+=a[i];
29     }
30     int l=minn,r=maxx;
31     while(l<r)
32     {
33         int mid=(l+r)>>1;
34         if(check(mid)) r=mid-1;
35         else l=mid+1;
36     }
37     printf("%d
",r);
38     return 0;
39 }

View Code