记录编号	593145	评测结果	AAAAA
题目名称	[Tyvj国庆欢乐赛] 山头狙击战	最终得分	100
用户昵称	1nclude	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2024-08-23 01:16:02	内存使用	3.98 MiB

#include<bits/stdc++.h>
#define get(x) if(sizeof(x)==8){scanf("%lld",&x);}else{scanf("%d",&x);}
#define put(x) if(sizeof(x)==8){printf("%lld",x);}else{printf("%d",x);}
using namespace std;

int n,m;
int arr[100005]={};
int arr2[100005]={};

bool can(int k)
{
	memcpy(arr2,arr,sizeof(arr));
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(arr2[i]<=m) 
		{
			cnt=(arr[i]-arr2[i])+k;
			arr2[i+1]-=cnt;
		}else{
			arr2[i]-=(arr2[i]-m);
			cnt=(arr[i]-arr2[i])+k;
			arr2[i+1]-=cnt;
		} 
		if(arr2[i]<0) return 0;
	}
	return 1;
}

int main()
{
 	freopen("battle.in","r",stdin);
	freopen("battle.out","w",stdout);
	get(n);get(m);
	for(int i=1;i<=n;i++)
	{
		get(arr[i]);
	}
	sort(arr+1,arr+1+n);
	int l=1,r=5000000;
	while(l<r)
	{
		int m=(l+r+1)>>1;
		if(can(m)) l=m;
		else r=m-1;
	}
	put(l);
    return 0;
}