题目描述

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

输入输出格式

输入格式：

 

第一行两个数n，m。

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1：

6 27 8 1 4 3 2

输出样例#1：

077113

说明

【数据规模】

m≤n≤2000000

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

正好昨天上课，教了这道题，下课后就到洛谷上搜题（习惯），结果找到了（哈哈）！

咳咳，废话不多讲，讲思路。

显然本题不可能是每次从 m 个连续的数中找最小值，那样肯定是超时的，那如

何思考呢？先来看看样例数据： 7 8 1 4 3 2 每次取某位置之前连续两个数中的最小

值。 （ 1）第 1 个位置之前没有值所以是 0，现在有了一个数 7；

（ 2）第 2 个位置之前只有一个数 7，故最小值为 7，现在有一两个数 7 8；

（ 3）第 3 个位置之前两个数为 7 8，最小值为 7；现在有三个数 7 8 1，当然由

于只要前面两个数，所以可以把 7 去掉，剩下 8 1，而由于求的是最小值，显然只需

要保留 1， 8 不可能是最小值了；

（ 4）第 4 个位置之前的最小值为 1，现在又加进来一个数 4，所以又有两个数 1

4； （ 5）第 5 个位置之前两个数 1 4，最小值为 7，现在又加进来一个数 3，当前由

于 1 已经不在范围内，所以去掉，处理 4 3，由于 3 比 4 小，则只保留最小值 3；

（ 6）第 6 个位置之前最小值为 3，又加进来 2，即为 3 2，由于 2 比 3 小，所以

只需要保留 2 就可以了。

一个单调队列，解决！

C++代码上……

#include
     
       using namespace std;const int maxN=2000000;int q[maxN+1][2]={0},n,m,head=0,tail=0;//q[i][0]表示值， q[i][1]表示在原来顺序的位置int main() {    scanf("%d%d", &n, &m);    printf("0\n"); 第1个数前没有数，输出0    scanf("%d", &q[tail][0]); //第1个数进队列    tail++;    for(int i=1; i
      
       m) head++;        printf("%d\n", q[head][0]); //输出队首元素（最小）        int x;        scanf("%d", &x);        while(tail>head&&x