USACO 2010 Feb Silver 3.Chocolate Eating 吃巧克力

2019-11-08 01:47:14

字体：大中小

来源：转载

供稿：网友

题目大意

Bessie拿到了N (1 <= N <= 50,000)块巧克力。她决定想个办法吃掉这些巧克力，使得它在吃巧克力的这段时间里，最不开心的一天尽可能的开心。并且一共吃D (1 <= D <= 50,000)天。每块巧克力有一个开心值H_i (1 <= H_i <= 1,000,000)，当某天你吃下那块巧克力时，你将获得那块巧克力的开心值。每一天的开心值是所有当天吃掉的巧克力的总开心值之和。每天晚上Bessie睡觉之后，它的开心值会减半。也就是说，比如昨天Bessie的开心值为50，那么今天早上我一醒来我就会有25点的开心值，舍去小数点后数字。另外，Bessie还有一个怪癖，她喜欢按照巧克力本来的排列顺序吃。 Bessie第一天的开心值为0，求一个每天吃巧克力的方案，使得Bessie最不开心的一天尽可能的开心。

算法

很明显，这是个二分，而坑的是要开long long 而check（）函数要从天数来枚举，时间快，代码好写。

二分正确写法（之一）

int find(int l,int r){ int mid,ans; while(l<r){ mid=(l+r)>>1; if(check(mid))l=mid+1; else r=mid; ans=l-1; } return ans;}

注意l要等于mid+1，而ans=l-1。

贴代码

#include <cstdio>#include <cstring>#include <algorithm>#include <cmath> using namespace std;long long a[50010];long long an[50010];long long n,d;bool check(long long x){ long long temp=0; long long now=1; for(int i = 1;i <= d;i++){ temp >>= 1; while(now <= n && temp < x) temp += a[now++]; if(temp < x)return false; } return true;}long long find(long long l,long long r){ long long mid,ans; while(l<r){ mid=(l+r)>>1; if(check(mid))l=mid+1; else r=mid; ans=l-1; } return ans;}int main(){ scanf("%lld%lld",&n,&d); long long sum=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum += a[i]; } long long ans=find(0,sum); PRintf("%lld/n",ans); long long temp=0; long long now=1; for(int i = 1;i <= d;i++){ temp >>= 1; while(now <= n && temp < ans){ temp += a[now++]; an[now - 1] = i; } } for(int i = 1;i <= n;i++){ if(an[i] == 0)printf("%lld/n",d); else printf("%lld/n",an[i]); }}

上一篇：POJ3109-Inner Vertices-离散化+扫描线

下一篇：线程池ExecutorService

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注