bzoj1639[Usaco2007 Mar]Monthly Expense 月度开支*

 2023-09-05 阅读 90 评论 0

摘要:bzoj1639[Usaco2007 Mar]Monthly Expense 月度开支 题意: n天,每天有一个花费,现在要将它们分成连续的m段,要求所有段的总花费的最大值最小。求这个值。n,m≤100000 题解: 二分花费,小于二分值的天作为一段。注意二分的下界

bzoj1639[Usaco2007 Mar]Monthly Expense 月度开支

题意:

n天,每天有一个花费,现在要将它们分成连续的m段,要求所有段的总花费的最大值最小。求这个值。n,m≤100000

题解:

二分花费,小于二分值的天作为一段。注意二分的下界应该是每天花费的最大值。

代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 100100
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 using namespace std;
 7 
 8 inline int read(){
 9     char ch=getchar(); int f=1,x=0;
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
12     return f*x;
13 }
14 int n,m,mon[maxn],l,r,ans;
15 bool check(int x){
16     int y=1,z=0;
17     inc(i,1,n){
18         if(z+mon[i]>x){y++; z=mon[i]; if(y>m)return 0;}else z+=mon[i];
19     }
20     return 1;
21 }
22 int main(){
23     n=read(); m=read(); inc(i,1,n)mon[i]=read(),l=max(l,mon[i]),r+=mon[i];
24     while(l<=r){
25         int mid=(l+r)>>1; if(check(mid))ans=mid,r=mid-1;else l=mid+1;
26     }
27     printf("%d",ans); return 0;
28 }

 

20160731

转载于:https://www.cnblogs.com/YuanZiming/p/5732466.html

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/4/1039.html

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息