10pts求助!

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

shiroko2008 @ 2022-01-24 21:23:36

手造了几组数据,然鹅自己hack不掉

#include<iostream>
#include<cstring>
using namespace std;
int search(long long* a,long long i,long long j,bool b) {
    long long ans=a[i];
    if (b) {for (long long k=i;k<=j;k++) if (a[k]>=ans) ans=a[k];}
    else {for (long long k=i;k<=j;k++) if (a[k]<=ans) ans=a[k];}
    return ans;
}
int main()
{
    long long n,k;
    cin>>n>>k;
    long long a[n];
    for (auto &c:a) cin>>c;
    long long i=0,j=k-1;
    long long minn=search(a,i,j,0),maxn=search(a,i,j,1);
    while (j<n) {
        cout<<minn<<" ";
        if (a[i]==minn) minn=search(a,(1+i),(j+1),0);
        i++;
        j++;
        if (a[j]<minn) minn=a[j];
    }
    cout<<endl;
    i=0,j=k-1;
    while (j<n) {
        cout<<maxn<<" ";
        j++;
        if (a[j]>=maxn) maxn=a[j];
        i++;
    }
    return 0;
}

by yzh_Error404 @ 2022-01-24 21:25:17

所以您不能好好写单调队列吗?


by Dream_weavers @ 2022-01-24 21:25:43

草,我把这题做成了ST表


|