单调队列算法,最后2个点WA,求调
查看原帖
单调队列算法,最后2个点WA,求调
178195
人间温柔楼主2025/6/24 16:14
#include<bits/stdc++.h>
using namespace std;

const int maxn=1000005;
const int maxm=10005;

int n,m,c,t;
int a[maxn];
bool flag=false;
int q1[maxm],head1=0,tail1=1;//单调递增的单调队列,求最小值 
int q2[maxm],head2=0,tail2=1;//单调递减的单调队列,求最大值 
//tail---------head
int main(){
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		while(head1>=tail1 && a[q1[head1]]>=a[i]) head1--;
		while(head1>=tail1 && i-q1[tail1]+1>m) tail1++;
		q1[++head1]=i;
		
		while(head2>=tail2 && a[q2[head2]]<=a[i]) head2--;
		while(head2>=tail2 && i-q2[tail2]+1>m) tail2++;
		q2[++head2]=i;
		
		if(i>=m && a[q2[tail2]]-a[q1[tail1]]<=c){
			cout<<i-m+1<<endl;
			flag=true;
		}
	}
	if(flag==false){
		cout<<"NONE"<<endl;
	}
	return 0;
}
2025/6/24 16:14
加载中...