会员专享
请先
登录 ，登录后可使用今日免费解锁；
开通会员 后可解锁完整内容。
枚举朴素解法
这道题的正解是 单调栈 单调栈 单调栈 暴力枚举所有长度为 k 的子序列取最大 暴力枚举所有长度为 k 的子序列取最大 暴力枚举所有长度为 k 的子序列取最大
题意：在保持相对顺序的前提下，从码流中选出恰好 k k k k k k error。
朴素做法：用 DFS / 回溯枚举「选或不选」当前元素，最终恰好选满 k k k O ( C ( n , k ) ⋅ k ) O(C(n,k)\cdot k) O ( C ( n , k ) ⋅ k )
样例和很小的 n n n n n n 2000 2000 2000 k k k
题目内容
手机接收来自网络侧的一条码流，该码流由多个子包依次组成，每个子包拥有一个用十进制非负整数表示的子包 ID。给定数组 n u m s nums n u m s
现在需要从码流中选出一个长度为 k k k k k k
两个长度相同的子包 ID 集合按如下规则比较优先级：从左到右逐位比较对应元素，在第一个出现不同元素的位置上，如果 a a a b b b a a a b b b [ 2 , 5 , 8 ] [2,5,8] [ 2 , 5 , 8 ] [ 2 , 4 , 9 ] [2,4,9] [ 2 , 4 , 9 ] 5 5 5 4 4 4 [ 2 , 5 , 8 ] [2,5,8] [ 2 , 5 , 8 ]
任务：在所有长度为 k k k
约束条件：
第一行码流中的子包 ID 数量不超过 2000。
每个子包 ID 的范围为 0 ≤ n u m s [ i ] < 500 0 \le nums[i] < 500 0 ≤ n u m s [ i ] < 500
需要选出的长度 k k k 1 ≤ k ≤ n u m s . l e n g t h 1 \le k \le nums.length 1 ≤ k ≤ n u m s . l e n g t h
输入描述
输入共两行。
第一行包含若干个用空格分隔的十进制非负整数，表示原始码流中的子包 ID。
第二行包含一个十进制正整数 k k k
如果无法读取完整两行、某一行为空，或某一行含有除十进制数字字符和空格以外的其他字符，则视为错误输入。
输出描述
对于合法输入，输出一行，将优先级最高的子包 ID 集合中的 k k k
对于错误输入，输出 error。
样例1
输入
3 1 2 5 4
3
输出
3 5 4
说明
原始码流为 [ 3 , 1 , 2 , 5 , 4 ] [3, 1, 2, 5, 4] [ 3 , 1 , 2 , 5 , 4 ] k = 3 k=3 k = 3
首元素如果取 5，后面只剩 [4]，数量不足以再选 2 个 ID，所以首元素最大可取 3。首元素为 3 时，第二个元素最大可取 5，此时后面还剩 [4]，刚好选满。
因此优先级最高的集合为 [3, 5, 4]，输出 3 5 4。
样例2
输入
1 5 2 5 3
1
输出
5
说明
当 k = 1 k=1 k = 1 1 个子包 ID。
此时优先级比较退化为单个数值比较，数值越大优先级越高。码流中的最大 ID 是 5，因此输出 5。
虽然码流中有两个 5，但输出数值不受位置影响。
样例3
输入
2 9 3 8 7
5
输出
2 9 3 8 7
说明
需要选出的长度 k = 5 k=5 k = 5 5。
因此不能删除任何子包，所有 ID 必须按原顺序全部保留。
所以输出原码流 2 9 3 8 7。
