3_甲基吲哚 @ 2019-11-07 18:46:35
单调队列做法,不知道为什么才20分
样例有一个地方跑不过去
样例输出:-1 -3 -3 -3 3 3
3 3 5 5 6 7
这个程序输出:-1 -3 -3 -3 5 3
3 3 5 5 6 7
//单调队列模板
//写点注释希望半期考后我还记得要点
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
int a[MAXN],h=1,t,b[MAXN];//a是双端队列,b也是,共用ht,b存a中元素的序号
int c[MAXN],d[MAXN];//用来求最大值
int s[MAXN];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++){//求最小值
while(s[i]<=a[h]&&h<=t)//有元素且不符合单调就踢掉队尾
t--;
a[++t]=s[i];
b[t]=i; //这里t就不用++了
if(b[h]<=i-k)//过时就踢掉
h++;
if(i>=k)//达到窗口了才出解
cout<<a[h]<<" ";
}
cout<<endl;
h=1;t=0;
for(int i=1;i<=n;i++){//复制求最大值
while(s[i]>=c[h]&&h<=t)
t--;
c[++t]=s[i];
d[t]=i;
if(d[h]<=i-k)
h++;
if(i>=k)
cout<<c[h]<<" ";
}
return 0;
}
求助
by Victorique_De_Blois @ 2019-11-07 18:54:11
(为什么不用线段树呢
by Lskkkno1 @ 2019-11-07 18:59:08
@真香
应该先踢队头
by 3_甲基吲哚 @ 2019-11-07 19:12:22
@Lskkkno1 可是试了先删队头还是一样呀
by ctq1999 @ 2019-11-07 19:35:09
@真香
同志,是:
while(s[i]<=a[t]&&h<=t)//有元素且不符合单调就踢掉队尾
s[i] <= a[t]
和队尾比较哦
by ctq1999 @ 2019-11-07 19:35:59
@真香
实测AC了
帮我点个赞呗
https://www.luogu.org/problemnew/solution/P2268
by 3_甲基吲哚 @ 2019-11-08 07:19:14
@ctq1999 十分感谢,已赞