再次求助

P1440 求m区间内的最小值

CSP_Sept @ 2020-02-13 14:30:32

这次用的是队列

#include <cstdio>
#include <queue>
using namespace std;
int l,r;
struct node{
    int num,index;
};
queue <node> D;
int n,m;
int main(){
    l=0;r=0;
    int tmp;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&tmp);
        node t;
        t.index=i,t.num=tmp;
        D.push(t);
        node x=D.front();
        if(tmp<=x.num){
            D.pop();
        }
        if(i==0) printf("0\n");
        else printf("%d\n",x.num);
        if(x.index+m==i) D.pop();
    }
    return 0;
}

by yangrunze @ 2020-02-13 14:41:44

@CSP_Sept 这个题要用双端队列的说

(你的单调队列为啥我看着怪怪的)


by PrincessQi @ 2020-02-13 15:05:03

线段树它不香吗


|