【洛谷P1886】滑动窗口——单调队列

没想到啊没想到,时隔两个月,我单调队列又懵了……

调了一个小时,最后错在快读,啊!!!!(不过洛谷讨论真好啊,感谢大佬!)

考前就不推新东西了,好好写写那些学过的东西


题目点这里(我就不粘了自己点一下看吧)

这题还有其他奇奇怪怪的做法,比如你可以当做RMQ,用线段树啊ST表啊随便你,不过单调队列就可以了

单调队列说到底就是个数据结构,就是维护数据的。

以当前这道题为例:

它维护的队列一定满足单调性,单调递增或递减,或者自定义一个单调性。

如何维护呢,假设当前队尾为q [ tail ], 要插入元素为 a [ i ]

  • 若直接插入 a [ i ] 满足其单调性,就直接插入
  • 若不满足,就删掉 q [ tail ] ( tail - - ) ,因为能取到 q [  tail ] 就一定能取到 a [ i ] , 而a [ i ] 更优

这题既然要求最大值和最小值,就求两遍嘛!

下面是代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,k,a[],q[],p[],head,tail;
inline int read()
{
int x=;
char c=getchar();
int flag=;
while (c>''||c<'')
{
if (c=='-')
flag*=-;
c=getchar();
} //就是这里!!!!记住它!!!
while (c<=''&&c>='') x=x*+c-,c=getchar();
x*=flag;
return x;
}//这个坑死我的快读啊!!!!!!考前一定要多打几遍
int main()
{
n=read(); k=read();
for (int i=; i<=n; i++)
a[i]=read();
// 求 min
head=; tail=;
for (int i=; i<=n; i++)
{
while (head<=tail&&q[tail]>=a[i])
tail--;
//首先保证不要删过,head<=tail(tail可以等于head)
//求最小那么单调性就是单调递增
q[++tail]=a[i];
p[tail]=i;//插入队列
while (p[head]<=i-k) head++;//更新队头,使最值在区间内
if (i>=k) cout<<q[head]<<" ";//k往后每一个i都对应一个窗口,输出队头存储的最值即可
}
cout<<endl;
head=,tail=;
// 求 max ,类比求 min
for (int i=; i<=n; i++)
{
while (head<=tail&&q[tail]<=a[i])
tail--;
//最大值就是单调递增
q[++tail]=a[i];
p[tail]=i;
while (p[head]<=i-k) head++;
if (i>=k) cout<<q[head]<<" ";
}
return ;//快考试啦不要抄答案!!!(给我自己
}

就是这些,CSP快到啦,RP++!!

惯例

ありがとうございます

上一篇:Unity 游戏开发技巧集锦之使用cookie类型的纹理模拟云层的移动


下一篇:安装oracle 10g RAC执行的几个脚本说明