求助大佬，90分，wa第二个点

guang_zi_guei_ji @ 2024-08-03 13:22:02

#include<iostream>
using namespace std;
const int N=10e6;
int a[N],n,m,b[N],b1[N],l=0,r=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    l=1;
    r=1;
    for(int i=1;i<=n;i++){
        while(b1[r]<i-m+1)r++;
        while(b[l-1]>a[i]&&l-1>=r)l--;
        b[l]=a[i];
        b1[l++]=i;
        if(i>=m)cout<<b[r]<<' ';
    }
    l=1;
    r=1;
    cout<<'\n';
    for(int i=1;i<=n;i++){
        while(b1[r]<i-m+1)r++;
        while(b[l-1]<a[i]&&l-1>=r)l--;
        b[l]=a[i];
        b1[l++]=i;
        if(i>=m)cout<<b[r]<<' ';
    }
    return 0;
}

by qi_shui @ 2024-08-03 20:35:48

第13行和23行需要判断队列不为空 改成

while(b1[r]<i-m+1&&l-1>=r)

by Kazuha_feywaye @ 2024-08-03 20:37:24

#include<iostream>
using namespace std;
const int N=10e6;
int a[N],n,m,b[N],b1[N],l=0,r=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    l=1;
    r=1;
    for(int i=1;i<=n;i++){
        if(l-1>=r&&b1[r]<i-m+1)r++;//一次就可以了 并且也要保证队列不空 
        while(b[l-1]>a[i]&&l-1>=r)l--;
        b[l]=a[i];
        b1[l++]=i;
        if(i>=m)cout<<b[r]<<' ';
    }
    l=0;
    r=0;//恢复成初始值 
    cout<<'\n';
    for(int i=1;i<=n;i++){
        if(l-1>=r&&b1[r]<i-m+1)r++;//同上
        while(b[l-1]<a[i]&&l-1>=r)l--;
        b[l]=a[i];
        b1[l++]=i;
        if(i>=m)cout<<b[r]<<' ';
    }
    return 0;
}

这样改就过了

by WuDiFengShu12345 @ 2024-08-04 16:28:56

求关注

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int n,k,a[N];
deque<int> dq;
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        while(dq.size() && dq.front()<i-k+1) dq.pop_front();
        while(dq.size() && a[dq.back()]>=a[i]) dq.pop_back();
        dq.push_back(i);
        if(i>=k) printf("%d ",a[dq.front()]);
    }
    cout<<endl;
    dq.clear();
    for(int i=1;i<=n;i++)
    {
        while(dq.size() && dq.front()<i-k+1) dq.pop_front();
        while(dq.size() && a[dq.back()]<=a[i]) dq.pop_back();
        dq.push_back(i);
        if(i>=k) printf("%d ",a[dq.front()]);
    }
    return 0;
}