问题 B: 滑动最小值

时间限制: 1 Sec  内存限制: 128 MB

提交: 127  解决: 27

[] [] [] [命题人:]

题目描述

给定一个长度为 n 的数列 a

₀,a

₁,,⋯,a

_n−1和一个整数k。求数列 b

_i=min(a

_i,a

_i+1 ,⋯,a

_i+k−1)(i∈[0,n))。

特别的，对于 i>n−k 的 b

_i=0。

 

输入

第一行两个正整数n，k。

第二行n个正整数a。

 

输出

n个数b。

 

样例输入

复制样例数据

5 21 2 3 4 5

样例输出

1 2 3 4 0

 

提示

对于100%的数据，n≤1000000。

#include
      
       #define REP(i, a, b) for(int i = (a); i <= (b); ++ i)#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)#define PER(i, a, b) for(int i = (a); i >= (b); -- i)#define REP(i, a, b) for(int k = (a); k <= (b); ++ k)using namespace std;template 
       
        inline void rd(T &ret){    char c;    ret = 0;    while ((c = getchar()) < '0' || c > '9');    while (c >= '0' && c <= '9'){        ret = ret * 10 + (c - '0'), c = getchar();    }}const int maxn=1e2+6;int n,a[maxn],k,b[maxn];int p[maxn];int main(){    rd(n),rd(k);    for(int i=0;i
        
         =a[i]) tail--;            p[tail++]=i;            if(i-k+1>=0) {                b[i-k+1]=a[p[head]];                if(p[head]==i-k+1) head++;            }    }    for(int i=0;i