萌新求助qwq #2WA

shcweb @ 2019-09-16 13:10:37

#include <bits/stdc++.h>
using namespace std;
int n, k, num[1233333];
deque< pair<int, int> > q;
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> num[i];
    for(int i = 1; i <= n; i++)
    {
        while(!q.empty() && q.back().first <= i - k)
            q.pop_back();
        while(!q.empty() && q.front().second >= num[i])
            q.pop_front();
        q.push_front(make_pair(i, num[i]));
        if(i >= k)
            cout << q.back().second << ' ';
    }
    cout << endl;
    for(int i = 1; i <= n; i++)
    {
        while(!q.empty() && q.back().first <= i - k)
            q.pop_back();
        while(!q.empty() && q.front().second <= num[i])
            q.pop_front();
        q.push_front(make_pair(i, num[i]));
        if(i >= k)
            cout << q.back().second << ' ';
    }
    return 0;
}

by hater @ 2019-09-16 13:14:56

手写食用更佳

by fzwfzwfzw @ 2019-09-16 13:19:49

#include<bits/stdc++.h>
using namespace std;
deque <int> q;
deque <int> p;
int n,m;
int a[2000005];
int ans1[2000005],cnt1,ans2[2000005],cnt2;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    q.push_back(1);
    p.push_back(1);
    for(int i=2;i<=m;i++)
    {
        while(!p.empty()&&(i-p.front())>m)p.pop_front();
        while(!q.empty()&&(i-q.front())>m)q.pop_front();
        while(!q.empty()&&(a[i]<=a[q.back()]))q.pop_back();
        while(!p.empty()&&(a[i]>=a[p.back()]))p.pop_back();
        q.push_back(i);
        p.push_back(i);
    }

    for(int i=m+1;i<=n+1;i++)
    {
        while(!p.empty()&&(i-p.front())>m)p.pop_front();
        while(!q.empty()&&(i-q.front())>m)q.pop_front();
        cnt1++;
        ans1[cnt1]=a[q.front()];
        ans2[++cnt2]=a[p.front()];
        while(!q.empty()&&(a[i]<=a[q.back()]))q.pop_back();
        while(!p.empty()&&(a[i]>=a[p.back()]))p.pop_back();
        q.push_back(i);
        p.push_back(i);
    }
    for(int i=1;i<=cnt1;i++)
    {
        printf("%d ",ans1[i]);
    }
    cout<<endl;
    for(int i=1;i<=cnt2;i++)
    {
        printf("%d ",ans2[i]);
    }
    cout<<endl;
    return 0;
}

by fzwfzwfzw @ 2019-09-16 13:20:04

可能开小了吧

by shcweb @ 2019-09-16 13:24:15

emm我明白了 我刚才脑子抽了没清空deque QAQ