违规用户名59285 @ 2019-10-10 23:08:45
#include<cstdio>
#include<queue>
using namespace std;
int n,m;
struct point{
int v;
int no;
};
int tag;
point a[2000005];
deque<point> q;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].v);
a[i].no=i;
}
a[0].no=0;
a[0].v=0;
tag=-1;
while(tag<n-1)
{
tag++;
if(q.empty())
q.push_back(a[tag]);
else
{
while(q.front().no<tag-m+1)
q.pop_front();
if(a[tag].v<=q.front().v)
{
q.clear();
q.push_back(a[tag]);
}
else if(a[tag].v<=q.back().v)
{
while(a[tag].v<=q.back().v)
{
q.pop_back();
}
q.push_back(a[tag]);
}
else q.push_back(a[tag]);
}
if(tag==0)
{
q.pop_front();
printf("0\n");
}
else
printf("%d\n",q.front().v);
}
return 0;
}
那道滑动窗口也是re一个点 不明白呀。。。
by 千反田 @ 2019-10-11 06:37:38
在下面弹出队头/队尾元素的时候前面多加个!q.empty()才能保证队列不为空
by 千反田 @ 2019-10-11 06:37:53
@江沢铭路
by Haishu @ 2019-10-11 08:00:42
ID暴力
by 违规用户名59285 @ 2019-10-11 20:53:16
@风吹花烬 谢谢dalao 的确是这样 之前以为根据这些代码就省得判断是否为空了 看来是while那儿出了问题