NC24724 Chocolate Eating

Chocolate Eating"/>

NC24724 Chocolate Eating

题目链接

题目链接

题意

给出n个巧克力和天数d，每个巧克力可以加H[i]的快乐值，每过一天快乐值减半，求d天种最低的快乐值的最大值。

思路

• 二分答案
• 如果该天的快乐值小于x，就吃巧克力直到快乐值大于x，若巧克力不够，则该值不行
• 注意开long long！！！！！！！！！

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,d;
long long aa[50100];
long long judge(long long x)
{long long re=0;long long j=0;for(int i=0; i<d; i++){re/=2;while(re<x){if(j<n){re+=aa[j];j++;}elsereturn 0;}}return 1;
}
int main()
{cin>>n>>d;long long l=0,r=0;for(int i=0; i<n; i++){cin>>aa[i];r+=aa[i];}while(l<=r){long long  mid=(l+r)/2;if(judge(mid)){l=mid+1;}else{r=mid-1;}}cout<<r<<endl;long long j=0;long long re=0;for(int i=0; i<d; i++){re/=2;while(re<r&&j<n){re+=aa[j];j++;cout<<i+1<<endl;}}for(;j<n;j++){cout<<d<<endl;}
}