洛谷 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注