【题解】求m区间内的最值(ST表实现)

【题解】求m区间内的最值(ST表实现)

小鱼干 218 2022-12-02

求m区间内的最小值

题目描述

一个含有 nn 项的数列,求出每一项前的 mm 个数到它这个区间内的最小值。若前面的数不足 mm 项则从第 11 个数开始,若前面没有数则输出 00

输入格式

第一行两个整数,分别表示 nnmm

第二行,nn 个正整数,为所给定的数列 aia_i

输出格式

nn 行,每行一个整数,第 ii 个数为序列中 aia_i 之前 mm 个数的最小值。

样例 #1

样例输入 #1

6 2
7 8 1 4 3 2

样例输出 #1

0
7
7
1
1
3

提示

对于 100%100\% 的数据,保证 1mn2×1061\le m\le n\le2\times10^61ai3×1071\le a_i\le3\times10^7

题目分析

题面的描述很简单,目的很清晰,求出每个元素的前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的区间,所以只需算法阶段为 log2mlog_2^m 的值即可。用一列的数组来存放内容。

st[i] 最终表示从i开始,长为 2log2m2^{log_2^m} 的连续区间内的最值。

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;
}