首页 > 代码库 > BZOJ 1639: [Usaco2007 Mar]Monthly Expense 月度开支
BZOJ 1639: [Usaco2007 Mar]Monthly Expense 月度开支
Description
Farmer John是一个令人惊讶的会计学天才，他已经明白了他可能会花光他的钱，这些钱本来是要维持农场每个月的正常运转的。他已经计算了他以后N(1<=N<=100,000)个工作日中每一天的花费moneyi(1<=moneyi<=10,000)，他想要为他连续的M(1<=M<=N)个被叫做“清算月”的结帐时期做一个预算，每一个“清算月”包含一个工作日或更多连续的工作日，每一个工作日都仅被包含在一个“清算月”当中。 FJ的目标是安排这些“清算月”，使得每个清算月的花费中最大的那个花费达到最小，从而来决定他的月度支出限制。
Input
第一行：两个用空格隔开的整数：N和M
第2..N+1行：第i+1行包含FJ在他的第i个工作日的花费
Output
第一行：能够维持每个月农场正常运转的钱数
题解:
M<=N，如果分成<M个清算月满足要求，那么也可以分成M个清算月。
最大值最小，考虑二分。
二分一个ans。
然后模拟一下每一天尽量把钱用完，
得到一个需要的清算月数目cnt。
若cnt<=M合法，否则不合法。
代码:
#include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;typedef long long LL;LL a[100005],n,k;LL maxx=0;LL l,r;bool judge(LL x){ LL sum=0; LL cnt=0; for(int i=1;i<=n;i++){ if(sum+a[i]>x){ sum=a[i]; cnt++; if(cnt>k) return 0; }else{ sum+=a[i]; } } if(sum)cnt++; if(cnt<=k) return 1; else return 0;}LL sum;int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); maxx=max(maxx,a[i]); sum+=a[i]; } l=maxx-1,r=sum; while(r-l>1){ int m=(l+r)>>1; if(judge(m)){ r=m; }else l=m; } printf("%lld\n",r); return 0;}
BZOJ 1639: [Usaco2007 Mar]Monthly Expense 月度开支
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。