求助 三个点超时
查看原帖
求助 三个点超时
79543
一大楼主2023/7/21 23:58
#include<bits/stdc++.h>
using namespace std;
const int N=200000;

int n,x,a[N+5];
int maxn=-1;
void check(){
	int m[N+5];
	memcpy(m,a,sizeof(a));

	deque<pair<int,int> > q;
	q.push_front(make_pair(0,2*x));
	while(q.size()){
		int d=q.back().first;
		int t=q.back().second;
//		cout<<d<<' '<<t<<endl;
		q.pop_back();
		if(d>=n) continue;
		for(int i=d+1;t;i++){
			if(i>=n){
				if(i-d>maxn) maxn=i-d;
				return;
			}
			if(m[i]){
//				cout<<i<<"   "<<m[i]<<" "<<t<<endl;
				if(m[i]>=t){
					m[i]-=t;
					if(i-d>maxn) maxn=i-d;
					q.push_front(make_pair(i,t));
                    t=0;
					break;
				}else{
					int ss=t-m[i];
					if(i-d>maxn) maxn=i-d;
					q.push_front(make_pair(i,m[i]));
					m[i]=0;
					t=ss; 
				} 
			}
							
		}
//		cout<<"T:"<<t<<endl;
	}
}
int main(){
	cin>>n>>x;
	for(int i=1;i<=n-1;i++) cin>>a[i];
	check();
	cout<<maxn;
}
2023/7/21 23:58
加载中...