滑动最小值_李大同

滑动最小值

发布时间：2020-12-14 04:38:54 所属栏目：大数据来源：网络整理

导读：问题 B: 滑动最小值时间限制: 1 Sec?? 内存限制: 128 MB 提交: 127?? 解决: 27 [提交] [状态] [讨论版] [命题人: admin] 题目描述给定一个长度为 n 的数列 a 0 ,a 1 ,?,a n?1 和一个整数k。求数列 b i =min(a i ,a i+1 ,a i+k?1 )(i∈[0,n))。特别的，对

问题 B: 滑动最小值

时间限制: 1 Sec??内存限制: 128 MB
提交: 127??解决: 27
[提交] [状态] [讨论版] [命题人:admin]

题目描述

给定一个长度为 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 2
1 2 3 4 5

样例输出

1 2 3 4 0

提示

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

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i = (a); i <= (b); ++ i)
#define REP(j,b) for(int j = (a); j <= (b); ++ j)
#define PER(i,b) for(int i = (a); i >= (b); -- i)
#define REP(i,b) for(int k = (a); k <= (b); ++ k)
using namespace std;
template <class T>
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<n;i++)rd(a[i]);
    int head=0,tail=0;
    for(int i=0;i<n;i++) {
        while(head<tail && a[p[tail-1]]>=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<n;i++)printf("%d ",b[i]);
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!