xyvsvg @ 2022-10-31 11:27:03
单调队列写法:
#include<iostream>
#include<stack>
#include<string>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<climits>
#include<cstdio>
using namespace std;
int n, m, a[2000002], q[2000002], h, t;
int main()
{
scanf("%d%d", &n, &m);
h = t = q[1] = 1;
scanf("%d", &a[1]);
printf("0\n");
for (int i = 2; i <= n; ++i)
{
scanf("%d", &a[i]);
if (q[h] + m < i)++h;
while (h <= t && a[i - 1] <= a[q[t]])--t;
q[++t] = i - 1;
printf("%d\n", a[q[h]]);
}
return 0;
}
while循环那行本来写的是while (h <= t && a[i - 1] < a[q[t]])--t;,结果改成<=就对了,不过我觉得这应该不会影响什么。但是为什么会过呢?
by xyvsvg @ 2022-10-31 11:27:27
@Ioencgc 改成<=之前wa了两个点