题解 | 整点巧克力

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4+10;

int n,d,h[N],l,r; 
vector<int> ans_path,res_path;

bool check(int mid){
	int current_happiness=0,th=1;
	for(int i=1;i<=d;i++){
		current_happiness/=2;
		while(current_happiness<mid){
			ans_path.push_back(i);
			current_happiness+=h[th];
			th++;
			if(th>n+1) return false;
		}
	}
	return true;
}

void solve(){
	
	int mid,res=0;
	while(l<=r){
		mid=l+r>>1;
		ans_path.clear();
		if(check(mid)){
			l=mid+1;
			res_path=ans_path;
			res=max(res,mid);
		}else{
			r=mid-1;
		}
	}
	
	cout<<res<<endl;
	for(int path:res_path){
		cout<<path<<endl;
	}
	for(int i=res_path.size();i<n;i++){
		cout<<d<<endl;
	}
	
	return;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>d;
	
	for(int i=1;i<=n;i++){
		cin>>h[i];
		r=r+h[i];
	}
	
	solve();
	
    return 0;
}