80分

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

某kob在此 @ 2022-01-16 18:14:06

不解，救助

# include <bits/stdc++.h>
using namespace std;

struct num
{
    int p, s;
};

int n, k;
int a[1000005];

int head, tail;
num q1[1000005], q2[1000005];

int main(void)
{
    cin >> n >> k;

    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    head = tail = 1;
    q1[1] = q2[1] = (num){1, a[1]};
    for (int i = 2; i <= n; i ++)
    {
        tail ++;
        q1[tail] = (num){i, a[i]};
        if (q1[tail].p - q1[head].p == k)
            head ++;
        while (q1[tail - 1].s >= q1[tail].s && tail - 1 >= head)
        {
            q1[tail - 1] = q1[tail];
            tail --;
        }
        if (i >= k) cout << q1[head].s << " ";
    }
    cout << endl;

    head = tail = 1;
    for (int i = 2; i <= n; i ++)
    {
        tail ++;
        q1[tail] = (num){i, a[i]};
        if (q1[tail].p - q1[head].p == k)
            head ++;
        while (q1[tail - 1].s <= q1[tail].s && tail - 1 >= head)
        {
            q1[tail - 1] = q1[tail];
            tail --;
        }
        if (i >= k) cout << q1[head].s << " ";
    }
    cout << endl;

    return 0;
}

by Studyingwinner @ 2022-01-16 19:33:43

满分代码:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
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 Inscription_Assassin @ 2022-01-16 20:42:10

@LAG_cdxxlhy 我并不推荐你直接粘满分代码，讨论区不能乱发AC代码，被举报党举报了可就不有趣了，而且回答问题针对帖主的问题回答，帖主自己会看题解的

|