给定一个长度为 n 的数列 a0,a1,,?,an−1和一个整数k。求数列 bi=min(ai,ai+1 ,?,ai+k−1)(i∈[0,n))。
特别的，对于 i>n−k 的 bi=0。
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, 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 <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]); }
原文：https://www.cnblogs.com/czy-power/p/10463066.html