发生了什么……

_FILARET_ @ 2018-10-07 10:07:50

#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
const int MAXN=1000005;
deque<int> dq;
int N, K;
int a[MAXN];
int main()
{
    cin>>N>>K;
    for(int i=0;i<N;i++)
    {
        cin>>a[i];
    }
    dq.push_back(0);
    cout<<dq.front()<<endl;
    for(int i=1;i<N;i++)
    {
        while(a[i]<a[dq.back()]) dq.pop_back();
        dq.push_back(i);
        while(dq.front()<i-K) dq.pop_front();
        cout<<a[dq.front()]<<endl;
    }
    return 0;
}

by wxy_god @ 2018-10-07 10:09:05

@deadpool123 那也得臭不要脸的交一次

by _FILARET_ @ 2018-10-07 10:10:01

@我是一个垃圾 不要现在我AC率太低了

by wxy_god @ 2018-10-07 10:10:33

@deadpool123 那就让我来交

by wxy_god @ 2018-10-07 10:10:55

然鹅全部RE

by Aleph1022 @ 2018-10-07 10:11:48

要判断队列为空的时候

不然会非法访问

by Aleph1022 @ 2018-10-07 10:11:52

@deadpool123

by _FILARET_ @ 2018-10-07 10:12:58

@I_love_him52 改了以后还是不行……

by _FILARET_ @ 2018-10-07 10:15:26

#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
const int MAXN=1000005;
deque<int> dq;
int N, K;
int a[MAXN];
int main()
{
    cin>>N>>K;
    for(int i=0;i<N;i++)
    {
        cin>>a[i];
    }
    dq.push_back(0);
    cout<<dq.front()<<endl;
    for(int i=1;i<N-1;i++)
    {
        while(a[i]<a[dq.back()]&&!dq.empty()) dq.pop_back();
        dq.push_back(i);
        while(dq.front()<i-K&&!dq.empty()) dq.pop_front();
        cout<<a[dq.front()]<<endl;
    }
    return 0;
}

by _FILARET_ @ 2018-10-07 10:34:40

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <deque>
#pragma GCC optimize (2)
#pragma GCC optimize (3)
using namespace std;
const int MAXN=2000005;
deque<int> dq;
int N, K;
int a[MAXN];
inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    } while('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}
inline void print(int x)
{
    int buf[100];
    int p=0;
    if(x<0){
        putchar('-');
        x=-x;
    }
    do{
        buf[p++]=x%10;
        x/=10;
    }while(x);
    for(int i=p-1;i>=0;i--) putchar(buf[i]+'0');
}
int main()
{
    N=read();
    K=read();
    a[0]=0;
    for(int i=1;i<=N;i++)
    {
        a[i]=read();
    }
    cout<<0<<endl;
    for(int i=1;i<N;i++)
    {
        while(!dq.empty()&&a[i]<a[dq.back()]) dq.pop_back();
        dq.push_back(i);
        while(!dq.empty()&&dq.front()<i-K+1) dq.pop_front();
        print(a[dq.front()]);
        cout<<endl;
    }
    return 0;
}