给大家来点不一样的队列解法（时间，空间复杂度均为O(n) )

注：本题和#P1886. 滑动窗口 /【模板】单调队列十分相似

上代码：

#include<iostream>
#include<queue>
using namespace std;
queue<int> q;
int l,tl=1,r,maxs,sum,n,m;// l,r,maxs为最终答案 ,tl记录当前队列中队首元素的在数组中的位置,sum记录当前队列中的元素和 
int a[19198100];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){//遍历数组a 
		q.push(a[i]);//插入队尾 
		sum+=a[i];//更新元素和 
		while(sum>m){//超过了m!pop队尾的元素把sum位置控制在m以下 (只能pop队首,不然会破坏元素的连续性) 
			sum-=q.front();//更新元素和 
			q.pop();
			tl++;//更新当前队列中队首元素的在数组中的位置
		}
		if(sum>maxs){//出现了更优解！更新答案 
			maxs=sum;
			r=i;
			l=tl;
		}
	}
	cout<<l<<' '<<r<<' '<<maxs;
	return 0;
}

思路源于洛谷上的题解,可以去看原文

思路:

本题要求的是不大于m的最大子序列的值，起始位置，终止位置

且如果有多个相同值，要取起始位置最小的 为满足起始位置尽量小，且在O(nlogn)的时间内(n最大为4*1e6),我们考虑使用数据结构-栈

栈的特点是先进先出，符合求起始位置的要求

所以,我们可以使用一个动态计数变量(以i作终止位置时的最大值)和一个栈(栈的长度为当前最大值所覆盖的长度

过程:

当栈加入一个值时，计数变量入一个值时,需要马上减至计数变量的值<=m且要进行出栈

while (计数变量 > m) {
			计数变量 -= 栈顶; //栈顶表示当前加的值
			出栈
		}

当计数变量>max(当前最大值)时，更新当前起始位置和终止位置

if (计数变量 > 最大值变量) {
			终止位置 = i;
			起始位置 = 终止位置 - 栈的长度 + 1;//栈的长度表示当前序列长度 
			更新最大值 
		}

总结:

本题所涉及的前缀和知识(计数变量)需与栈结合使用

打个广告，可以给个点赞吗？
在线悬赏【[HNOI2003] 激光炸弹】点差评者！！，赏金1元