q1

_just_do_it_ · 2025-08-04 09:28:57 · 个人记录

#include<iostream>
#include<cstring>
using namespace std;
int n,k,q[1000001],a[1000001],id[1000001];
void MIN(){
    int head=1,tail=0;
    memset(q,0,sizeof q);
    memset(id,0,sizeof id);
    for(int i=1;i<=n;i++){
        while(head<=tail&&q[tail]>a[i])tail--;
        q[++tail]=a[i];
        id[tail]=i;
        while(head<=tail&&id[head]<i-k+1)head++;
        if(i>=k)cout<<q[head]<<" ";
    }
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(1){
        cin>>n>>k;
        if(n==0&&k==0){
            return 0;   
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        MIN();  
    }

    return 0;
}