Wangyuqi2010 @ 2024-10-14 13:05:18

#include<iostream>
#include<deque>
using namespace std;
struct node{
    int id;
    int num;
};
deque<node>Q1;
deque<node>Q2;
int n,k;
int a[1000010];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    Q1.push_front( {1,a[1]} );
    for(int i=2;i<=n;i++){
        while(Q1.back().num>=a[i]&&!Q1.empty()) Q1.pop_back();
        Q1.push_back( {i,a[i]} );
        if(Q1.front().id<=i-k){
            Q1.pop_front();
        }
        if(i>=k){
            cout<<Q1.front().num<<' ';
        }

    }
    cout<<endl;
    Q2.push_front( {1,a[1]} );
    for(int i=2;i<=n;i++){
        while(Q2.back().num<=a[i]&&!Q2.empty()) Q2.pop_back();
        Q2.push_back({i,a[i]});
        if(Q2.front().id<=i-k){
            Q2.pop_front();
        }
        if(i>=k){
            cout<<Q2.front().num<<' ';
        }
    }
    return 0;
} 

by lch1218 @ 2024-10-19 21:25:34

你为什么一定要用那个结构体呢？

by lch1218 @ 2024-10-19 21:26:39

你就用int 类型数据不好吗？直接队尾维护啊，用了struct反而麻烦

by lch1218 @ 2024-10-19 21:28:09

ac代码 cpp

include<bits/stdc++.h>

using namespace std;

define int long long

int n,k; int a[1000010],b[1000010],c[1000010]; deque<int> q; deque<int> dq; signed main(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ while(!q.empty() && a[q.back()]>a[i]) q.pop_back(); q.push_back(i); if(i>k){ if(i-k+1>q.front()){ q.pop_front(); } } if(i>=k) b[i]=a[q.front()]; } for(int i=1;i<=n;i++){ while(!dq.empty() && a[dq.back()]<a[i]) dq.pop_back(); dq.push_back(i); if(i>k){ if(i-k+1>dq.front()){ dq.pop_front(); } } if(i>=k) c[i]=a[dq.front()]; } for(int i=k;i<=n;i++) cout<<b[i]<<' '; cout<<endl; for(int i=k;i<=n;i++) cout<<c[i]<<' '; return 0; }

by lch1218 @ 2024-10-19 21:29:05

搞错了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int a[1000010],b[1000010],c[1000010];
deque<int> q;
deque<int> dq;
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        while(!q.empty() && a[q.back()]>a[i])           q.pop_back();
            q.push_back(i);
        if(i>k){
            if(i-k+1>q.front()){
                q.pop_front();
            }
        }
        if(i>=k)    b[i]=a[q.front()];
    }
    for(int i=1;i<=n;i++){
        while(!dq.empty() && a[dq.back()]<a[i]) dq.pop_back();
        dq.push_back(i);
        if(i>k){
            if(i-k+1>dq.front()){
                dq.pop_front();
            }
        }
        if(i>=k)    c[i]=a[dq.front()];
    }
    for(int i=k;i<=n;i++)   cout<<b[i]<<' ';
    cout<<endl;
    for(int i=k;i<=n;i++)   cout<<c[i]<<' ';
    return 0;
}

by nod1212 @ 2024-10-24 20:19:41

3 1
1 1 1

你的输出:

1 1
1 1

正确输出：

1 1 1
1 1 1