10pts求调

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

lyq123bc @ 2024-04-18 19:54:55

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+50;
int x;
deque<pair<int,int> >Q;
deque<pair<int,int> >R;
int maxx[N],minn[N];

int main()
{
    int n,m,k,sum=1;
    scanf("%d%d",&n,&k);
    pair<int,int>lin;//lin.first编号,lin.second大小
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        lin.first=i; lin.second=x;
        while(!Q.empty()&&x>Q.back().second) Q.pop_back();
        while(!R.empty()&&x>R.back().second) R.pop_back();
        Q.push_back(lin); R.push_back(lin);
        while((i-k)>=Q.front().first) Q.pop_front();
        while((i-k)>=R.front().first) R.pop_front();
        if(i>=k)
        {
            maxx[sum]=Q.front().second;
            minn[sum]=R.front().second;
            ++sum;
        }
    }
    for(int i=1;i<sum;++i) printf("%d ",minn[i]);
    printf("\n");
    for(int i=1;i<sum;++i) printf("%d ",maxx[i]);

    return 0;
}

WA 9个点


by TMLY114514 @ 2024-05-06 19:16:46

第19行 < 写成 >


by lyq123bc @ 2024-06-01 13:24:35

@TMLY114514 3Q


|