求助!!70分

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

wyl123ly @ 2023-07-21 20:26:24

为啥啊两个WA一个TLE

#include<bits/stdc++.h>
using namespace std;
long long int a[1000000];
int max(long long int a[10000],long long int k1,long long int k2){
    long long int k=k1,num=-2100000,cnt=0;
    while(cnt<k2-k1){
        if(a[k]>num){
            num=a[k];
        }
        k++;
        cnt++;
    }
    return num;
}
int min(long long int a[10000],long long int k1,int k2){
    long long int k=k1,num=21000000,cnt=0;
    while(cnt<k2-k1){
        if(a[k]<num){
            num=a[k];
        }
        k++;
        cnt++;
    }
    return num;
}
int main(){
    long long int n,k,ma,mi;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    cin>>a[i];
    }
    for(int i=1;i<=n-k+1;i++){
        mi=min(a,i,i+k);
        printf("%d ",mi);
    }
    cout<<endl;
    for(int i=1;i<=n-k+1;i++){
        ma=max(a,i,i+k);
        printf("%d ",ma);
    }
    return 0;
}
  • 大佬们帮忙改一下

by QBW1117 @ 2023-08-07 09:27:05

这个暴力能拿70pts我很佩服

你的时间复杂度是O(nk)

数据稍大会T


|