野外探险 描述

小明正在参加一个为期D天的野外探险活动，他带了N份干粮，干粮按顺序编号，小明按编号从小到大开始吃，总共花费D天将其全部吃完。每份干粮有一个能量值Hi，当某天小明吃下一份干粮时，他就获得了这份干粮的能量，每一天获得的能量是这一天小明吃下的所有干粮的能量值之和。但是这个能量经过一个夜晚的消耗，在第2天早上时会失去一半。比如昨天小明获得能量值之和是100，那么今天小明在没有吃新干粮前他拥有的能量值是50（这里采用整除方式，即假如昨天能量为9，那么今天早上就剩下了4，而不是4.5）。现在请你帮小明设计一个方案，尽量让小明获得能量值最小的那一天越大越好。

4 野外探险.in

4 野外探险.out

输入 输入第1行两个整数N和D；

输入第2行一共N个整数，第i个整数Hi表示第i份干粮能提供的能量值。

输出 输出一行一个整数，表示小明获得能量值最少那一天的最大值。

输入样例 1

5 5 10 40 13 22 7 输出样例 1

24 输入样例 2

4 7 58 4 31 83 输出样例 2

23 提示

样例1解释：

第1天吃第1块和第2块巧克力，此时获得的能量值为10+40=50;

第2天不吃巧克力，此时获得的能量值是第一天的一半，50/2=25;

第3天吃第3块巧克力，此时获得的能量值是第2天的一半再加上13，即25/2+13=25;

第4天吃第4块巧克力，此时获得的能量值是第3天的一半再加上22，即25/2+22=34;

第5天吃第5块巧克力，此时获得的能量值是第4天的一半再加上7，即34/2+7=24;

1≤N,D≤5×10^4;

1≤Hi≤10^6;

0分超时代码

using namespace std;
const int N=5e4+5;
long long n,d,l=1,r=1e18,mid;
long long a[N]; 
bool cheak(long long x){
	long long cnt=0,ans=0;
	for(int i=1;i<=d;i++){
		ans/=2;
		while(cnt<=n&&ans<x){
			ans+=a[i];
			cnt++;
		}
	}
	return cnt<=n;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		l=min(l,a[i]);
		r=max(r,a[i]);
	}
	while(l<=r){
		mid=(l+r)/2;
		if(cheak(mid)){
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	long long ans=0;
	for(int i=1;i<=d;i++){
		ans/=2;
		while(ans<l){
			ans+=a[i];
		}
	}
	cout<<ans;
	return 0;
}