天宇1105 @ 2020-10-13 13:57:02
#include <bits/stdc++.h>
using namespace std;
int n,k,q[1000001],e[1000001];
int head=0,tail=0;
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
q[head]=0;
for (int i = 0; i < n; ++i)
{
cin>>e[i];
}
if(k==1)
for (int i = 0; i < n; ++i)
{
cout<<e[i]<<" ";
}
else
for (int i = 0; i < n; ++i)
{
if (i-q[head]>=k)
{
head++;
}
while((head<=tail)&&(e[q[tail]]>e[i])) tail--;
tail++;
q[tail]=i;
if(i>=k-1)cout<<e[q[head]]<<" ";
}
cout<<endl;
head=0,tail=0;
if(k==1)
for (int i = 0; i < n; ++i)
{
cout<<e[i]<<" ";
}
else
for (int i = 0; i < n; ++i)
{
if (i-q[head]>=k)
{
head++;
}
while((head<=tail)&&(e[q[tail]]<e[i])) tail--;
tail++;
q[tail]=i;
if(i>=k-1)cout<<e[q[head]]<<" ";
}
return 0;
}
by wsyhb @ 2020-10-13 16:36:03
@天宇1105
手工队列中一开始有元素 if
删除滑出窗口的
给一组 Hack 数据(本人手造):
Input
5 3
1 2 3 4 5
Output
1 2 3
3 4 5
/*
代码输出
1 1 2
3 4 5
*/
解决方法有两种:
head=1,tail=0
代码(评测记录)
while
删除元素代码(评测记录)
话说这竟然能得 90 分
by 天宇1105 @ 2020-10-13 18:08:35
谢谢了