十分求调 , 九WA

P1440 求m区间内的最小值

zxyaa @ 2022-10-18 13:11:51

#include<bits/stdc++.h>
using namespace std;
struct node{
    int zhi;
    int number;
};
deque<node> qx;
int small[2000005];
node q;
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        q.zhi=x;
        q.number=i;
        while(!qx.empty()&&x<=qx.back().zhi){
            qx.pop_back();
        }
        qx.push_back(q);
        if(qx.front().number+k<=i){
            qx.pop_front();
        } 
        if(i>=k){
            small[i-k+2]=qx.front().zhi;
        }
    }
    for(int i=1;i<=n-k+1;i++){
        cout<<small[i]<<endl;
    }
    return 0;
}

by Sylvia_starx @ 2022-10-18 13:27:07

非要用队列吗?


by zxyaa @ 2022-10-18 14:09:52

em.......不是


by Sylvia_starx @ 2022-10-18 15:10:18

@zxyaa 用dp[]简单点吧


by zxyaa @ 2022-10-18 17:05:41

啊??,我不会用dp[]写呜呜呜呜


by zxyaa @ 2022-10-20 17:27:53

求调求调,单调队列,大佬救我


by PhiliaTheCat @ 2023-01-24 21:57:51

你好像读错题了。具体怎么改的话,可以参照一条关于读错题的讨论,里面有解释。


|