单调队列不行???
查看原帖
单调队列不行???
964402
AaBbCcDdEeFf5500楼主2023/11/9 16:40

怎么看这道题都像一个滑动窗口啊,为什么就WA了呢 。。。

蒟蒻代码求调

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m, c;
int a[N], q[N];
int ma[N], mi[N];
int idx;

int main()
{
    scanf("%d%d%d", &n, &m, &c);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++)
    {
    	if(hh <= tt && i - m + 1 > q[hh]) hh ++;
    	while(hh <= tt && a[i] <= a[q[tt]]) tt --;
    	q[++ tt] = i;
    	if(i >= m - 1) ma[++ idx] = a[i];
    }
    
    hh = 0, tt = -1, idx = 0;
    for(int i = 1; i <= n; i ++)
    {
    	if(hh <= tt && i - m + 1 > q[hh]) hh ++;
    	while(hh <= tt && a[i] >= a[q[tt]]) tt --;
    	q[++ tt] = i;
    	if(i >= m - 1) mi[idx ++] = a[i];
    }
	
	bool flag = true;
	for(int i = 1; i <= idx; i ++)
		if(abs(ma[i] - mi[i]) <= c)
			cout << i << endl, flag = false;
			
	if(flag) puts("NONE");
	
	return 0;
}
2023/11/9 16:40
加载中...