蓝桥模拟

蓝桥模拟

title: 蓝桥模拟_第十题_晚会节目单
categories:

• ACM
• RMQ
  tags:
• ST
  date: 2020-03-27 18:20:44

频繁的查询区间最值对于遍历来说开销非常大，所以产生了一种区间最值查询这种算法，本文只讲ST+RMQ，ST是稀疏矩阵的意思，这种方法要求数据必须是静态的不能变化的。

问题引入

有一个一位数组(长度为n)，频繁的查询[s,e]区间的最值。

算法详解

定义一个二维数组ST(大小[n,lgn])。ST[i][j]表示的是从i开始(包括i)向后2^{j个元素区间的最值，即区间[i,i+2}j-1]的最值，那么很明显ST[i][0]=a[i](因为[i,i]只有一个值)。现在我们开始推导递推式,[i,i+2^{j-1]可以按照中间分为两个大小为2}(j-1)的区间[i,i+2^{(j-1)-1]和[i+2}(j-1),i+2^{j-1]，那么[i,i+2}j-1]的最值为这两个区间再求最值，即[i,i+2^{j-1]=min/max([i,i+2}(j-1)-1],[i+2^(j-1),i+2j-1])也就是：

ST[i][j]=min/max(ST[i][j-1],ST[i+2^j][j-1])

那么就可以发现第j列某个元素值的计算只跟它前一列的某两个值有关，并且刚刚我们已经算好了第一列，由第一列可以计算第二列，由第二列可以计算第三列……那么要算到哪一列呢？ST[i][j]表示的区间是[i,i+2^{j-1]很明显i+2}j-1<=n-1(n个元素，下标0~n-1)所以就有了建ST的模板：

void cal(int a[],int n)
{for(int i=0;i<=n-1;i++)ST[i][0]=a[i];for(int j=1;(1<<(j))<=n;j++){for(int i=0;i+(1<<j)-1<=n-1;i++){st[i][j]=max/min(st[i][j-1],st[i+1<<(j-1)][j-1]);}}	
}

说了半天有了这个表该怎么用呢？假如我们要计算区间[s,e]的最值该怎么算呢？我们能够利用的是ST[此处可为任意数][此处必须为2的幂]如果我们能够找到一个k，使得区间[s,e]变成[s,s+2^{k-1]和`[s+2^k][e]`，我们就可以利用表了，但是你会发现第二个区间没法表示，我们只能表示长度为2的幂的区间。于是聪明人就会发现用e减去2的幂不就行了！于是将[s,e]变成[s,s+2}k-1]和[e-2^k+1,e]，这样区间[s][e]的最值就可以变为min/max(ST[s][k],ST[e-2^K+1][e])但是可能有人又会提出疑问了，如果这两个集合没有交集怎么办？比如[2,6]分为[2,3]和[5,6] (k=1)，这样得到话明显不对啊！所以我们需要找一个比较大的k值，[s,s+2^{k-1]必须包含在`[s][e]`里面,也就是s+2}k-1<=e 解得
k < = l o g 2 ( e − s + 1 ) , 令 k = l o g 2 ( e − s + 1 ) k<=log_2(e-s+1),令k=log_2(e-s+1) k<=log2​(e−s+1),令k=log2​(e−s+1)
并且(int)k去除了k的小数部分，也就是说0<=k-(int)k<1，所以k-1<(int)k<=k，代入原式：
2 k − 1 − 1 < 2 ( i n t ) k − 1 < = 2 k − 1 将 k = l o g 2 ( e − s + 1 ) 代 入 得 2^{k-1}-1<2^{(int)k}-1<=2^k-1将k=log_2(e-s+1)代入得 2k−1−1<2(int)k−1<=2k−1将k=log2​(e−s+1)代入得

( e − s ) / 2 − 1 / 2 < 2 ( i n t ) k − 1 ， 此 处 2 ( i n t ) k − 1 是 整 数 ， 所 以 ( e − s ) / 2 = < 2 ( i n t ) k − 1 (e-s)/2-1/2<2^{(int)k}-1，此处2^{(int)k}-1是整数，所以(e-s)/2=<2^{(int)k}-1 (e−s)/2−1/2<2(int)k−1，此处2(int)k−1是整数，所以(e−s)/2=<2(int)k−1

所 以 s + 2 ( i n t ) k − 1 > = s + ( e − s ) / 2 = ( e + s ) / 2 ( 中 点 ) 且 e − 2 k + 1 < = e − ( e + s ) / 2 = ( e + s ) / 2 ( 中 点 ) 所以s+2^{(int)k}-1>=s+(e-s)/2=(e+s)/2(中点)且e-2^k+1<=e-(e+s)/2=(e+s)/2(中点) 所以s+2(int)k−1>=s+(e−s)/2=(e+s)/2(中点)且e−2k+1<=e−(e+s)/2=(e+s)/2(中点)

所以当k=(int)(log2(e-s+1))时，ST[s][k],ST[e-2^K+1][e]表示的区间一定有交集。所以要求[s,e]区间最值只需要计算min/max(ST[s][k],ST[e-2^K+1][e]),k=(int)(log2(e-s+1))

例题

第十题 晚会节目单

题目

【问题描述】

小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。
这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。
小明发现，观众对于晚会的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。
小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。

【输入格式】

输入的第一行包含两个整数 n, m ，表示节目的数量和要选择的数量。
第二行包含 n 个整数，依次为每个节目的好看值。

【输出格式】

输出一行包含 m 个整数，为选出的节目的好看值。

【样例输入】

5 3
3 1 2 5 4

【样例输出】

3 5 4

【样例说明】

选择了第1, 4, 5个节目。

【评测用例规模与约定】

对于 30% 的评测用例，1 <= n <= 20；
对于 60% 的评测用例，1 <= n <= 100；
对于所有评测用例，1 <= n <= 100000，0 <= 节目的好看值 <= 100000。

思路 O(N^2)

ST+RMQ

参考代码

#include<cstdio>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#define PP(a,b) cout<<a<<"="<<b<<endl
#define P(a) cout<<a<<endl
#define print(a) cout<<#a<<"="<<a<<endl
#define _for(i,s,e) for(int i=s;i<=e;i++)
using namespace std;
int n,m;
int a[100001];
int st[100001][20];
void cal(int a[],int n)
{for(int j=1;(1<<(j-1))<=n;j++){for(int i=0;i+(1<<j)-1<=n-1;i++){st[i][j]=max(st[i][j-1],st[i+1<<(j-1)][j-1]);}}	
}
int query(int s,int e)
{int t=(int)(log(e-s+1)/log(2));return max(st[s][t],st[e-(1<<t)+1][t]);
} 
int main()
{	//freopen("input.txt","r",stdin);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;_for(i,0,n-1){cin>>a[i];st[i][0]=a[i];}cal(a,n);int s=0,k=m;while(k!=0){int z=query(s,n-1-k+1);cout<<z<<" ";s=z+1;k--;}        	  
}