AC却不知为何

P1440 求m区间内的最小值

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了两个点


|