【蓝桥杯】压轴题：晚会节目单(给定长度的字典序最大子序列) RQM算法详解_输入格式】 第一行包含两个整数 和 ,表示备选嘉宾数量和需要邀请嘉宾的数量; 第二-CSDN博客

　　第十题 晚会节目单

　　题目

　　【问题描述】

　　小明要组织一台晚会，总共准备了 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。

　　错误思路:想着从n个数据中选择m个最大的,按照原顺序输出

　　举例:1

　　10 7

　　10 56 59 41 69 66 6 76 15 50

　　如果按照错误想法应该输出:

　　56 59 41 69 66 76 50

　　可是正确的应该是:

　　59 69 66 6 76 15 50

　　即,希望前几个数尽可能的大,而后面有几个小的也无所谓

　　所以这个题可以转化成求n个数字的序列中选出m个且字典序最大

　　思路一: 穷举(不推荐)

　　m选n个数,如果当前的大于之前的最大的则更新

　　dfs回溯法,二进制状压法

　　思路二:

　　在保障最后有数字可以取的情况下,在当前范围取最大值

　　时间复杂度:最多选n次,每次最多进对n个数选最大的

　　如果是线性时间选择O(n)情况时间复杂度大概是n^2

　　如果用RMQ算法(一种动态规划算法,有点类似于归并排序的思想),先预处理,得出各个范围的最大值,时间复杂度nlogn,然后进行查询时间复杂度是m*O(1)二者相加也是O(nlogn)

　　RMQ（Range Minimum/Maximum

　　Query），即区间最值查询。RMQ算法一般用较长时间做预处理，时间复杂度为O(nlogn)，然后可以在O（1）的时间内处理每次查询。

　　1.求范围为L的区间上最大值

　　2.如果下标计算啥的不好推的话,举个例子就看懂了