求调

roumeideclown @ 2023-06-12 19:23:23

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000001];
deque<int> q;
void do_min() {
    for(int i=1;i<=n;i++) {
        while(!q.empty()&&a[q.back()]>a[i]) {
            q.pop_back();
        }
        q.push_back(i);
        while(!q.empty()&&i-q.front()>k) {
            q.pop_front();
        }
        if(i>=k) {
            cout<<a[q.front()]<<' ';
        }
    }
    cout<<'\n';
    return;
}
void do_max() {
    for(int i=1;i<=n;i++) {
        while(!q.empty()&&a[q.back()]<a[i]) {
            q.pop_back();
        }
        q.push_back(i);
        while(!q.empty()&&i-q.front()>k) {
            q.pop_front();
        }
        if(i>=k) {
            cout<<a[q.front()]<<' ';
        }
    }
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    do_min();
    while(!q.empty()) {
        q.pop_front();
    }
    do_max();
    return 0;
}

by fwtv_24 @ 2023-06-12 19:45:21

10分应该是样例分

验证码mqct祭

by _zzzzzzy_ @ 2023-06-12 19:52:40

@roumeideclown

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000001];
deque<int> q;
void do_min() {
    for(int i=1;i<=n;i++) {
        while(!q.empty()&&a[q.back()]>=a[i]) {//换不换都行
            q.pop_back();
        }
        q.push_back(i);
        while(!q.empty()&&i-q.front()>=k) {//
            q.pop_front();
        }
        if(i>=k) {
            cout<<a[q.front()]<<' ';
        }
    }
    cout<<'\n';
    return;
}
void do_max() {
    for(int i=1;i<=n;i++) {
        while(!q.empty()&&a[q.back()]<=a[i]) {//这个也是
            q.pop_back();
        }
        q.push_back(i);
        while(!q.empty()&&i-q.front()>=k) {//
            q.pop_front();
        }
        if(i>=k) {
            cout<<a[q.front()]<<' ';
        }
    }
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    do_min();
    while(!q.empty()) {
        q.pop_front();
    }
    do_max();
    return 0;
}