用的单调队列RE一个点。。。

ｃｈｉｌｌ @ 2018-03-08 17:36:47

#include <bits/stdc++.h>
using namespace std;

deque <int> Q;
int n,m,a[3000001];

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    printf("0\n");
    for (int i=1;i<n;i++)
        {
            if (i-Q.front()>=m) Q.pop_front();
            while (!Q.empty()&&a[i]<=a[Q.back()]) Q.pop_back();
            Q.push_back(i);         
            printf("%d\n",a[Q.front()]);
        }
    return 0;
}

by ｃｈｉｌｌ @ 2018-03-08 17:40:05

是deque容器的问题吗

by colazcy @ 2018-06-02 15:46:09

将

if (i-Q.front()>=m) Q.pop_front();

移动到printf语句之前

#include <bits/stdc++.h>
using namespace std;

deque <int> Q;
int n,m,a[3000001];

int main()
{
    scanf("%d%d",&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()&&a[i]<=a[Q.back()]) Q.pop_back();
            Q.push_back(i);     
            if (i-Q.front()>=m) Q.pop_front();
            printf("%d\n",a[Q.front()]);
        }
    return 0;
}

by Juanzhang @ 2018-07-25 10:13:44

@colazcy %%%

by colazcy @ 2018-07-25 13:59:57

@小光 您您您太强啦

by Juanzhang @ 2018-07-25 19:45:07

@colazcy fAKe