救救孩子

arekilldog @ 2019-08-16 11:42:35

#include<bits/stdc++.h>
using namespace std;
deque<int> k1,k2;
vector<int> a;
int n,m,kk;

void Init(){
    cin>>n>>m;
    a.push_back(0);
    for(int i=1;i<=n;i++)
    {   
        cin>>kk;
        a.push_back(kk);
    }

}
int main(){
    Init();
    k1.push_back(a[1]);
    for(int i=2;i<=n;i++)
    {
        if(a[i]>k1.back())
        {
            k1.push_back(a[i]);
        }
        else
        {
            while(k1.empty()!=true&&a[i]<k1.back())
            {
                k1.pop_back();
            }
            k1.push_back(a[i]); 
        }
        if(i>=m)
        {
        cout<<k1.front()<<' ';
            if(k1.front()==a[i-m+1])
            {
                k1.pop_front();
            }
        }
    }
    cout<<endl;
    k2.push_back(a[1]);
    for(int i=2;i<=n;i++)
    {
        if(a[i]<k2.back())
        {
            k2.push_back(a[i]);
        }
        else
        {
            while(k2.empty()!=true&&a[i]>k2.back())
            {
                k2.pop_back();
            }
            k2.push_back(a[i]); 
        }
        if(i>=m)
        {
        cout<<k2.front()<<' ';
            if(k2.front()==a[i-m+1])
            {
                k2.pop_front();
            }
        }
    }
    return 0;
}
/*
8 3
1 3 -1 -3 5 3 6 7
*/

by arekilldog @ 2019-08-16 11:43:47

显示是（输出7，输出了个负数），这是咋回事，其他点都ac了？？

by 生而为人 @ 2019-08-16 11:53:06

@arekilldog 您 能 用线段树 吗

by arekilldog @ 2019-08-16 11:57:12

@生而为人 很抱歉 不能orz

by arekilldog @ 2019-08-16 11:57:29

@生而为人 没学过 线段树 啊

by 生而为人 @ 2019-08-16 11:58:00

@arekilldog 啥？ 线段树 维护 区间最值 不行？？

by 生而为人 @ 2019-08-16 11:59:48

@arekilldog 论好板子的重要性

// luogu-judger-enable-o2
#include<iostream>
#include<deque>
using namespace std;
int a[1000005];
int n,k;
deque <int> q;
deque <int> p;
void work1()
{
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&a[q.back()]>a[i])
        q.pop_back();
        while(!q.empty()&&i-q.front()>=k)
        q.pop_front();
        q.push_back(i);
        if(i>=k)
        cout<<a[q.front()]<<" ";
    }
}
void work2()
{
    for(int i=1;i<=n;i++)
    {
        while(!p.empty()&&a[p.back()]<a[i])
        p.pop_back();
        while(!p.empty()&&i-p.front()>=k)
        p.pop_front();
        p.push_back(i);
        if(i>=k)
        cout<<a[p.front()]<<" ";
    }
}
int main()
{
    ios::sync_with_stdio(false);

    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    work1();
    cout<<endl;
    work2();
    return 0;
}

by arekilldog @ 2019-08-16 12:07:29

@生而为人 但我就是百度也不懂线段树是什么啊qwq

by arekilldog @ 2019-08-16 13:10:08

救救孩子吧。。。 为什么单调队列会wa一个点