滑动窗口100最后一个点T了求调

P1886 滑动窗口 /【模板】单调队列

ayszYW @ 2024-07-16 15:12:24

rt

#include<bits/stdc++.h>
using namespace std;

int n,a[2100000],m,lans[2100000],lans2[2100000];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];

    int i=0,j=m-1;
    int ans=INT_MAX,ans2=-INT_MAX;

    for(int l=1;l<=m;l++)ans=min(ans,a[l]);
    for(int l=1;l<=m;l++)ans2=max(ans2,a[l]);
    while(j<n){
        //cout<<i<<" "<<j<<endl;
        j++;
        if(j-i==m){
            i++;
            if(a[i-1]==ans){
                ans=INT_MAX;
                for(int k=i;k<=j;k++)ans=min(ans,a[k]);
            }
            if(a[i-1]==ans2){
                ans2=-INT_MAX;
                for(int k=i;k<=j;k++)ans2=max(ans2,a[k]);
            }
        }
        if(a[j]<=ans)ans=a[j];
        lans[j]=ans;
        if(a[j]>=ans2)ans2=a[j];
        lans2[j]=ans2;

    }
    for(int i=m;i<=n;i++)cout<<lans[i]<<" ";
    cout<<'\n';
    for(int i=m;i<=n;i++)cout<<lans2[i]<<" ";

}

by YCN_AK_NOI @ 2024-07-16 15:16:48

@ayszYW 建议快读

by YCN_AK_NOI @ 2024-07-16 15:19:30

但好像不是这个原因,应该是一些细节问题

by YCN_AK_NOI @ 2024-07-16 15:21:03

这题不是要用单调队列吗

by ayszYW @ 2024-07-16 15:21:16

@YCN_AK_NOI cin断开同步流比快读快吧

by ayszYW @ 2024-07-16 15:23:11

@YCN_AK_NOI 乂？（我看题目是滑动窗口啊）

by Mugino_Shizuri @ 2024-07-16 15:40:27

@ayszYW 推荐算一下时间复杂度。

by Mugino_Shizuri @ 2024-07-16 15:43:46

@ayszYW 提供一组数据生成器。

#include<bits/stdc++.h>

using namespace std;

const int n=1e6;
const int m=2e5;

int main(){
    cout<<n<<' '<<m<<'\n';
    for(int i=1;i<=n;++i) cout<<n-i+1<<' ';cout<<endl;
    return 0;
}

by ayszYW @ 2024-07-16 16:14:51

@Mugino_Shizuri 谢谢，没看k取值范围，八嘎

|