只想说坑好多。。

两个任务，一个是通过二分输出正确的ans，另一个是输出顺序正确的方案。

check()不难写，memset一下记录日期的d[]...... 点击此处查看血的教训1

为了输出顺序正确的方案，需要再check()一遍...... 点击此处查看血的教训2

最后注意认真审题 “他要在接下来的M天内把能量石全部吃完” 在最后输出判断一下d[i]是否为0，若为0，则输出m。 点击此处查看血的教训3

（问题就在于样例并没有这种“特殊情况”，但是去看上面这个测评就会发现WA的点都输出了0，说明这个时候是需要特判的。

CODE

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int N=5e4+7;
int n,m,a[N],sum,d[N],ans;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
int check(int x){
	int cnt=0,sum=0;
	memset(d,0,sizeof d);//记得初始化!!!
	for(int i = 1;i<=m;i++){
		sum/=2;
		while(sum<x){
			sum+=a[++cnt];
			if(cnt==n+1)return 0;
			d[cnt]=i;
		}
	}
	return 1;
}
void checkagain(int x){
	int cnt=0,sum=0;
	memset(d,0,sizeof d);//记得初始化!!! 
	for(int i = 1;i<=m;i++){
		sum/=2;
		while(sum<x){
			sum+=a[++cnt];
			if(cnt==n+1)return;
			d[cnt]=i;
		}
	}
	return;
}
signed main(){
	n=read();m=read(); 
	for(int i = 1;i<=n;i++){
		a[i]=read();
		sum+=a[i];
	}
	int l=0,r=sum;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			l=mid+1;
			ans=mid;
		}else r=mid-1;
	}
	write(ans);putchar('\n');
	checkagain(ans);//为了让输出的方案顺序满足题意
	for(int i = 1;i<=n;i++){
		//记得"他要在接下来的M天内把能量石全部吃完"!!! 
		if(d[i]==0)write(m),putchar('\n');
		else write(d[i]),putchar('\n');
	}
	return 0;
}

首先我们可以看到这道题要求出一个最大值最小的值

那么我们直接想到二分

但是我们二分答案完成了之后要求给出一种方案使得字典序最大

那也就是说我们要让每个物品被使用的时间尽可能地晚

所以说我们可以在后面直接进行模拟，最后输出

时间复杂度 $O(N \times log(N \times E_i))$

#include<iostream>
#include<cstring>
#include<cstdio>
#define N 50005
#define int long long
using namespace std;
bool Test_MLE_start;
int T=1,n,m,ans=0;
int d[N],sum[N],bns[N];
bool Test_MLE_end;
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c-'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
bool check(int k){
	int ret=0,cnt=0;
	for(int i=1;i<=m;i++){
		ret/=2;
		while(ret<k){
			if(cnt<n) ret+=d[++cnt];
			else break;
		}
	}
	if(ret<k) return 0;
	return 1;
}
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	while(T--){
		n=reads(),m=reads();
		for(int i=1;i<=n;i++){
			d[i]=reads();
			sum[i]=sum[i-1]+d[i];
		}
		int L=0,R=sum[n];
		while(L<=R){
			int mid=(L+R)>>1;
			if(check(mid)){
				ans=mid;
				L=mid+1;
			}
			else R=mid-1;
		} 
		printf("%lld\n",ans);
		int now=0,cnt=1;
		for(int i=1;i<=n;i++){
			now+=d[i];
			printf("%lld\n",cnt);
			while(now>=ans&&cnt<m){
				now>>=1;
				cnt++;
			}
		}
	}
	return 0;
}