10pts求调（悬1关）

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

Ted_LightningTechG_ @ 2024-02-22 10:42:50

#include<bits/stdc++.h>
struct queu{
    int q[1000005];
    int h, t;
    queu() { h = t = 1; }
    inline void init() { h = t = 1; }
}que;
int n, k, a[1000005];
int main() {
    std::cin >> n >> k;
    for(int i = 1; i <= n; i ++) std::cin >> a[i];
    for(int i = 1; i < k; i ++) {
        que.q[++ que.t] = i;
        while(a[que.q[que.t]] < a[que.q[que.t - 1]] && que.t > que.h) que.q[que.t - 1] = que.q[que.t --];
    }
    for(int i = k; i <= n; i ++) {
        if(que.q[que.h] == i - k) que.h ++;
        que.q[++ que.t] = i;
        while(a[que.q[que.t]] < a[que.q[que.t - 1]] && que.t > que.h) que.q[que.t - 1] = que.q[que.t --];
        std::cout << a[que.q[que.h]] <<' ';
    }
    std::cout <<'\n';
    que.init();
    for(int i = 1; i < k; i ++) {
        que.q[++ que.t] = i;
        while(a[que.q[que.t]] > a[que.q[que.t - 1]] && que.t > que.h) que.q[que.t - 1] = que.q[que.t --];
    }
    for(int i = k; i <= n; i ++) {
        if(que.q[que.h] == i - k) que.h ++;
        que.q[++ que.t] = i;
        while(a[que.q[que.t]] > a[que.q[que.t - 1]] && que.t > que.h) que.q[que.t - 1] = que.q[que.t --];
        std::cout << a[que.q[que.h]] <<' ';
    }
    return 0;
}

强烈不建议使用Dev-C++调，因为Dev-C++里面输出是正确的，而luoguIDE就会输出错误答案

by 2023hkm @ 2024-02-22 11:11:43

AC代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int q1[1000001],q2[1000001];
int a[1000001];
int min_deque()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q1[h]+m<=i) h++;
        while(h<=t&&a[i]<a[q1[t]]) t--;
        q1[++t]=i;
        if(i>=m) printf("%d ",a[q1[h]]);
    }
    cout<<endl;
}
int max_deque()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q2[h]+m<=i) h++;
        while(h<=t&&a[i]>a[q2[t]]) t--;
        q2[++t]=i;
        if(i>=m) printf("%d ",a[q2[h]]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    min_deque();
    max_deque();
    return 0;
}

求关

by wangzhiqin @ 2024-02-22 12:22:01

@TedLightningTechG 哟，做滑动窗口啦666

by wayne_wei @ 2024-02-22 14:13:22

@TedLightningTechG 就你 ????????????

|