求调单调队列#6RE
查看原帖
求调单调队列#6RE
1101266
Fe_CuSO4__FeSO4_Cu楼主2025/1/11 10:24
#include <bits/stdc++.h>
using namespace std;
#define N 4000020
#define ll long long
#define bol bitset
#define imax INT_MAX
#define imin INT_MIN
#define inf 0x3f3f3f3f
#define B 100000010
#define min(a,b) (a<b ? a:b)
#define max(a,b) (a>b ? a:b)
int a[N];
deque<int>q,q1;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	printf("0\n");
	for(int i=1;i<=n;i++)
	{
		//单调队列
		while(!q.empty()&&q.back()>a[i]) q.pop_back(),q1.pop_back();
		//是否过期
		while(int(q1.front())<i-m) q.pop_front(),q1.pop_front();
		//特判
		if(i!=1) printf("%d\n",int(q.front()));
		q.push_back(a[i]);
		q1.push_back(i);
	}
	return 0;
}

如标题,只有#6RE,其他的AC。

2025/1/11 10:24
加载中...