优先队列40分，4wa求调

struct_cym @ 2023-10-04 09:14:31

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const int M=3e7+1;
priority_queue<int,vector<int>,greater<int> >q;
int flag[M];
int n,m;
int nums[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&nums[i]);
    }
    printf("0\n");
    for(int i=2;i<=n;i++){
        if(i>m+1){
            flag[nums[i-m-1]]=1;
        }
        q.push(nums[i-1]);
        while(flag[q.top()]){
            q.pop();
        }
        if(!flag[q.top()])
            printf("%d\n",q.top());
    }
    return 0;
}

by aochiao @ 2024-05-04 12:27:27

@struct_cym

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+1;
int a[maxn];
deque<int>q;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    printf("0\n");
    for(int i=2;i<=n;i++){
        while(!q.empty()&&a[q.back()]>a[i-1]) q.pop_back();
        q.push_back(i-1);
        while(!q.empty()&&q.front()<i-m) q.pop_front();
        printf("%d\n",a[q.front()]);
    }
    return 0;
}

by aochiao @ 2024-05-04 12:28:04

@struct_cym 求关注QwQ