求m区间内的最小值

题目描述

一个含有 $n$ 项的数列，求出每一项前的 $m$ 个数到它这个区间内的最小值。若前面的数不足 $m$ 项则从第 $1$ 个数开始，若前面没有数则输出 $0$ 。

输入格式

第一行两个整数，分别表示 $n$ ， $m$ 。

第二行， $n$ 个正整数，为所给定的数列 $a_i$ 。

输出格式

$n$ 行，每行一个整数，第 $i$ 个数为序列中 $a_i$ 之前 $m$ 个数的最小值。

样例 #1

样例输入 #1

6 2
7 8 1 4 3 2

样例输出 #1

提示

对于 $100\%$ 的数据，保证 $1\le m\le n\le2\times10^6$ ， $1\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的区间，所以只需算法阶段为 $log_2^m$ 的值即可。用一列的数组来存放内容。

st[i] 最终表示从i开始，长为 $2^{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;
}

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