Akira的OI(咸鱼)圈

单调队列

算法
Word count: 265 / Reading time: 1 min
2018/09/29 Share

贡献最大的元素放在队头，直至失效出队，队中所有比即将入队元素贡献值小的元素出队，因其无论如何不会比选即将入队元素更优，即将入队元素必定入队，因其时间上有优势，直至其后出现贡献值比他大的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define ll long long
#define maxn 1000001
using namespace std;
inline int read()
{
    int l=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        l=(l<<3)+(l<<1)+(ch^'0');
        ch=getchar();
    }
    return w*l;
}
struct pp
{
    int index,x;
};
int main()
{    
    deque<pp>q;
    int n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        pp k;
        k.x=read();
        k.index=i;
        if(q.empty())
            printf("0\n");
        else
        {
            if(q.front().index+m<i)
                q.pop_front();
            printf("%d\n",q.front().x);
        }
        while(!q.empty()&&q.back().x>k.x)
            q.pop_back();
        q.push_back(k);
    }
    return 0;
}

原文作者: Akira

原文链接: https://akira-1231.github.io/2018/09/29/单调队列/

发表日期: 九月 29日 2018, 11:23:59 上午

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 11
2018
题解 算法 杂记