求m区间内的最小值
题目描述
一个含有 项的数列,求出每一项前的 个数到它这个区间内的最小值。若前面的数不足 项则从第 个数开始,若前面没有数则输出 。
输入格式
第一行两个整数,分别表示 ,。
第二行, 个正整数,为所给定的数列 。
输出格式
行,每行一个整数,第 个数为序列中 之前 个数的最小值。
样例 #1
样例输入 #1
6 2
7 8 1 4 3 2
样例输出 #1
0
7
7
1
1
3
提示
对于 的数据,保证 ,。
题目分析
题面的描述很简单,目的很清晰,求出每个元素的前m个元素中的最小值。是一个连续区间内求最值的问题,此时能够想到使用ST表
解决RMQ
问题。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=2e6+1;
int st[N][22];
int n,m;
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&st[i][0]);
for(int j=1;j<=22;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
int k=log2(m);
printf("0\n");
for(int i=2;i<=n;i++){
int l=max(i-m,1),r=i-1;
int k=0;
k=log2(r-l+1);
printf("%d\n",min(st[l][k],st[r-(1<<k)+1][k]));
}
return 0;
}
提交后会发现会有测试点显示超空间,观察题目限制可发现空间限制比较严苛。那么我们需要尝试对空间进行优化。在对动态规划的空间优化中,我们有学习过滚动数组的空间优化,仔细观察状态转移过程,查看是否可用。
for(int j=1;j<=22;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
可发现每个st[i][j]
的内容,都由已确定的st[?][j-1]
的值决定,意味着,当前这列的值由上一列的值决定,无需考虑更前列的内容。由于最后只需考虑长为m
的区间,所以只需算法阶段为 的值即可。用一列的数组来存放内容。
st[i]
最终表示从i开始,长为 的连续区间内的最值。
int k=Log[m];
for(int j=1;j<=k;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i]=min(st[i],st[i+(1<<j-1)]);
}
}
代码实现
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2e6+5;
int st[N]; //一维ST表,滚动数组
int main() {
int n, m, ans = 3e7;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &st[i]);
if (i == 1) {//i等于1,前面没有元素
printf("0\n");
ans = st[i];
} else if (i <= m) {//当区间长度<m,可直接更新出最小值
ans = min(ans, st[i - 1]);
printf("%d\n", ans);
}
}
int k = log2(m);
//滚动数组更新长度为m的连续区间内的最值
for (int j = 1; j <= k; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[i] = min(st[i], st[i + (1 << j - 1)]);
}
}
for (int i = m + 1; i <= n; i++) {
ans = min(st[i - m], st[i - (1 << k)]);
printf("%d\n", ans);
}
return 0;
}