洛谷1440 求m区间内的最小值

本题地址：http://www.luogu.org/problem/show?pid=1440

题目描述

一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。

输入输出格式

输入格式：

第一行两个数n，m。
第二行，n个正整数，为所给定的数列。

输出格式：

n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。

输入输出样例

输入样例#1：

6 2

7 8 1 4 3 2

输出样例#1：

说明

【数据规模】
m≤n≤2000000

【思路】

单调队列。

题目比较裸，直接用一个单调队列维护即可。单调队列第一次写，总结有如下需要注意的地方：

1、
注意维护的是什么，本题中维护的是一个满足序号 >=i-m+1 的序列，其中序列满足a值单调递增。

2、
注意边界，特别是初始情况下是否平凡。

3、
注意单调队列的维护添加
与取值之间的顺序，取决于使用单调队列的目的。

还有需要注意的是题目中要求i之前m个，每次取值是算上当前a的所以需要错开一个。

【代码】

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int maxn = +;

 int a[maxn],que[maxn],d[maxn];

 int n,m,front,rear;

 inline int read_int() {

     char c; c=getchar();

     while(!isdigit(c)) c=getchar();

     int x=;

     while(isdigit(c)) {

         x=x*+c-'';

         c=getchar();

     }

     return x;

 }

 int main() {

     n=read_int(); m=read_int();

     a[]=<<;               //边界不取

     front=rear=;

     for(int i=;i<=n;i++)

     {

         a[i]=read_int();

         //注意顺序

         while(front<=rear && (que[front]<(i-m+))) front++;

         while(front<=rear && a[i]<=a[que[rear]]) rear--;  //注意维护a值最小的 

         que[++rear]=i;

         d[i]=a[que[front]];

     }

     cout<<<<"\n";

     for(int i=;i<n;i++) cout<<d[i]<<"\n";

     return ;

 }

秒客网

洛谷1440 求m区间内的最小值

相关文章