洛谷 P2251 【质量检测】题解

这一道题的主要思路:单调队列(不熟的可以做一下滑动窗口这一道题)

建立一个从小到大的单调队列,每次如果读入到比队尾的数小就将队尾的数弹出(贪心思想:你后面都有更小值的了你还要前面的干什么呢?反而长度更长更容易失效),另外不要忘了将已经超出整个序列长度的物体从队首弹出,的而每一组的答案就是这个单调队列的队首元素

代码如下:
#include<iostream>
#include<cstdio>
using namespace std;
int a[1000001];
struct node
{
int a;//物体的质量
int b;//物体的位置
}b[1000001];
int main()
{
int n,m,head=1,top=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=m;i++)//前m个数可以直接进入队列,不需要考虑超出长度的问题
{
while(head<=top&&b[top].a>=a[i])//将队尾较大元素弹出(建立单调队列)
top--;
b[++top].a=a[i];//将当前元素加入队列中
b[top].b=i;
}
cout<<b[head].a<<endl;//输出第一个序列中的最小值
for(int i=m+1;i<=n;i++)
{
while(head<=top&&b[head].b<=i-m)//将队首已经超出序列长度的元素弹出
head++;
while(head<=top&&b[top].a>=a[i])//将队尾较大元素弹出(建立单调队列)
top--;
b[++top].a=a[i];//将元素压入队列中
b[top].b=i;
cout<<b[head].a<<endl;//输出当前序列最小值
}
return 0;
}

评论

此博客中的热门博文