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

2019-11-08 01:47:14

字體：大中小

供稿：網(wǎng)友

題目大意

Bessie拿到了N (1 <= N <= 50,000)塊巧克力。她決定想個(gè)辦法吃掉這些巧克力，使得它在吃巧克力的這段時(shí)間里，最不開心的一天盡可能的開心。并且一共吃D (1 <= D <= 50,000)天。每塊巧克力有一個(gè)開心值H_i (1 <= H_i <= 1,000,000)，當(dāng)某天你吃下那塊巧克力時(shí)，你將獲得那塊巧克力的開心值。每一天的開心值是所有當(dāng)天吃掉的巧克力的總開心值之和。每天晚上Bessie睡覺之后，它的開心值會(huì)減半。也就是說，比如昨天Bessie的開心值為50，那么今天早上我一醒來我就會(huì)有25點(diǎn)的開心值，舍去小數(shù)點(diǎn)后數(shù)字。另外，Bessie還有一個(gè)怪癖，她喜歡按照巧克力本來的排列順序吃。 Bessie第一天的開心值為0，求一個(gè)每天吃巧克力的方案，使得Bessie最不開心的一天盡可能的開心。

算法

很明顯，這是個(gè)二分，而坑的是要開long long 而check（）函數(shù)要從天數(shù)來枚舉，時(shí)間快，代碼好寫。

二分正確寫法（之一）

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);