萌新刚学单调队列，咋就tle70分呢

P1440 求m区间内的最小值

blackfrog @ 2019-04-18 22:42:33

```cpp #include<iostream> #include<deque> #include<queue> using namespace std; long long n,m,mn = 99999999; struct element{ long long v,id; }; deque<element> a; int main(){ cin>>n>>m; a.push_back({99999999,0}); cout<<0<<endl; for(long long i = 1;i<n;i++){ long long x; cin>>x; if(x<a.back().v){ while(!a.empty()&&x<a.back().v){ a.pop_back(); } } a.push_back({x,i}); cout<<a.front().v<<endl; if(a.front().id==i-m+1)a.pop_front(); } return 0; } ```

by 紬文德斯 @ 2019-04-18 22:46:04

这个是能用优先队列的吗.....?

deque是不是优先队列啊

by blackfrog @ 2019-04-18 22:51:36

@紬文德斯 优先队列是priority_queue啊

by smarthehe @ 2019-04-18 23:13:05

#include<iostream>
#include<cstdio>
#include<deque>
#include<queue>
using namespace std;
int n,m,mn = 99999999;
struct element{
    int v,id;
};
deque<element> a;
int main(){
    scanf("%d%d",&n,&m);
    a.push_back({99999999,0});
    printf("0\n");
    for(register int i = 1;i<n;i++){
        int x;
        scanf("%d",&x);
        if(x<a.back().v){
            while(!a.empty()&&x<a.back().v){
                a.pop_back();
            }
        }
        a.push_back({x,i});
        printf("%d\n",a.front().v);
        if(a.front().id==i-m+1) a.pop_front();
    }
    return 0;
}

by smarthehe @ 2019-04-18 23:14:16

@blackfrog

long long 换 int

cin 换 scanf

cout 换 printf

就a了

要学学卡常啊

by blackfrog @ 2019-04-19 12:11:31

@smarthehe 感谢感谢！！

|