单调队列80WA求调

P1440 求m区间内的最小值

Chizuru_Ichinose @ 2023-10-19 19:31:47


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int kMax=2e6+5;
int n,k,a[kMax],t=1;
deque<int> q;   
signed main() {
    scanf("%lld%lld",&n,&k);
    for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
    cout<<0<<endl;
    for(int i=1; i<n; i++) {
        while(!q.empty() && a[i]<=q.back()) q.pop_back();
        q.push_back(a[i]);
        if(i-t>=k && q.front()!=a[t]) t++;
        else if(i-t>=k && q.front()==a[t]) {
            t++;
            q.pop_front();
        }
        printf("%lld\n",q.front());
    }
    return 0;
}

by HZHDCM @ 2023-10-19 20:42:35

%%%


by Chizuru_Ichinose @ 2023-10-23 19:55:42

@HZHDCM万猿身万德


|