最后一个数据点TLE,求助

P1886 滑动窗口 /【模板】单调队列

Suspicious_spy @ 2024-04-15 17:45:23

#include<iostream>
#include<deque>
#define swift ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

deque<int> que_max;
deque<int> que_min;
int a[1000005], res_min[1000005], res_max[1000005];

void POP(deque<int> & que, int val){
    if(!que.empty() && val == que.front())
        que.pop_front();
}

void push_min(deque<int> & que, int val){
    while(!que.empty() && val < que.back())
        que.pop_back();
    que.push_back(val);
}

void push_max(deque<int> & que, int val){
    while(!que.empty() && val > que.back())
        que.pop_back();
    que.push_back(val);
}

int result(deque<int> que){
    return que.front();
}

int main(){
    swift
    int count_min = 1, count_max = 1;
    int n, k;
    cin>>n>>k;
    for(int i = 1;i <= n;++i){
        cin>>a[i];
        push_min(que_min, a[i]);
        push_max(que_max, a[i]);
        if(i > k){
            POP(que_min, a[i - k]);
            POP(que_max, a[i - k]);
        }
        if(i >= k){
            res_min[count_min++] = result(que_min);
            res_max[count_max++] = result(que_max);
        }
    }
    for(int i = 1;i < count_min;++i)
        cout<<res_min[i]<<' ';
    cout<<endl;
    for(int i = 1;i < count_max;++i)
        cout<<res_max[i]<<' ';
    cout<<endl;
    return 0;
}

by kevinZ99 @ 2024-04-15 18:07:07

@Suspicious_spy

最好别用 deque ,这玩意效率非常快。快到你无法想象。


by wbhqm @ 2024-04-23 21:51:56

@Suspicious_spy 超出范围有点多了,应该是思路的问题


by Suspicious_spy @ 2024-04-24 16:45:03

@wbhqm 思路没问题吧,我把deque换成数组后过了, 提交记录: P1886 滑动窗口


by wbhqm @ 2024-04-28 21:15:55

@Suspicious_spy deque速度慢到超出想象,但正确的思路deque是可以a的


|