解题思路

题意：给定一串子包 ID（顺序不能改变），从中删去若干个子包，保留 恰好 k 个，得到的长度为 k 的子包集合按字典序（从左到右比较大小）要尽量大。 如果在第一个不同的位置上，集合 a 的数字大于集合 b 的数字，则 a 的优先级更高。

这就是“在数组中选出长度为 k 的字典序最大子序列”的经典问题，可以用 贪心 + 单调栈 来做。

做法：

1. 假设总长度为 n，需要删掉的元素个数为 drop = n - k。

2. 从左到右依次扫描每个子包 ID：

   • 维护一个栈（用数组或列表实现），栈中保存当前已经选择的子包 ID。

   • 对于当前元素 x：

     • 当 drop > 0 且栈不空且栈顶元素小于 x 时， 就可以把栈顶弹出（相当于删掉之前选的这个更小的 ID），drop--。
     • 之后把 x 压入栈。

3. 所有元素扫描完后，如果栈长度大于 k，就只保留前 k 个（因为可能没删够，但多的放在后面，截断即可）。

4. 栈中前 k 个元素就是字典序最大的长度为 k 的子序列。

此外，题目要求只接受 10 进制数字：

• 第一行和第二行中若出现非数字非空格字符（如 0x2 中的 x），则直接输出 error。

复杂度分析

设码流长度为 n。

• 时间复杂度：每个元素最多入栈一次、出栈一次，故为 O(n)。
• 空间复杂度：栈最多存下 n 个元素，故为 O(n)（结果长度为 k，k ≤ n）。

代码实现

Python

# 功能函数：返回长度为 k 的字典序最大子序列
def max_subsequence(nums, k):
    n = len(nums)
    drop = n - k  # 还能删除的个数
    stack = []
    for x in nums:
        # 贪心：当前元素更大且还能删除之前的元素，就弹栈
        while drop > 0 and stack and stack[-1] < x:
            stack.pop()
            drop -= 1
        stack.append(x)
    # 可能还没删够，多余的在后面，直接截断
    return stack[:k]


def is_valid_line(s):
    # 只允许数字和空白字符
    for ch in s:
        if not (ch.isdigit() or ch.isspace()):
            return False
    return True


def main():
    try:
        line1 = input().strip()
    except EOFError:
        print("error")
        return

    if not line1 or not is_valid_line(line1):
        print("error")
        return

    try:
        line2 = input().strip()
    except EOFError:
        print("error")
        return

    if not line2 or not is_valid_line(line2):
        print("error")
        return

    # 解析子包 ID 列表
    nums = list(map(int, line1.split()))
    # 解析 k
    k = int(line2)
    ans = max_subsequence(nums, k)
    # 按空格输出
    print(" ".join(str(x) for x in ans))


if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {

    // 功能函数：返回长度为 k 的字典序最大子序列
    public static int[] maxSubsequence(int[] nums, int k) {
        int n = nums.length;
        int drop = n - k;          // 还能删除的个数
        int[] stack = new int[n];  // 用数组模拟栈
        int top = 0;               // 栈中元素个数

        for (int x : nums) {
            // 贪心：当前元素更大且还能删除之前的元素，就弹栈
            while (drop > 0 && top > 0 && stack[top - 1] < x) {
                top--;
                drop--;
            }
            stack[top++] = x;
        }

        // 只需要前 k 个
        int[] res = new int[k];
        System.arraycopy(stack, 0, res, 0, k);
        return res;
    }

    // 检查一行是否只包含数字和空白
    public static boolean isValidLine(String s) {
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!Character.isDigit(ch) && !Character.isWhitespace(ch)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line1 = br.readLine();
        if (line1 == null || line1.trim().isEmpty() || !isValidLine(line1)) {
            System.out.println("error");
            return;
        }

        String line2 = br.readLine();
        if (line2 == null || line2.trim().isEmpty() || !isValidLine(line2)) {
            System.out.println("error");
            return;
        }

        // 解析子包 ID 列表
        StringTokenizer st = new StringTokenizer(line1);
        ArrayList<Integer> list = new ArrayList<Integer>();
        while (st.hasMoreTokens()) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        int n = list.size();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = list.get(i);
        }

        // 解析 k
        int k;
        try {
            k = Integer.parseInt(line2.trim());
        } catch (NumberFormatException e) {
            System.out.println("error");
            return;
        }
        int[] ans = maxSubsequence(nums, k);
        // 输出
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            if (i > 0) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 功能函数：返回长度为 k 的字典序最大子序列
vector<int> maxSubsequence(const vector<int>& nums, int k) {
    int n = (int)nums.size();
    int drop = n - k;        // 还能删除的个数
    vector<int> st;          // 当作栈使用
    st.reserve(n);

    for (int x : nums) {
        // 贪心：当前元素更大且还能删除之前的元素，就弹栈
        while (drop > 0 && !st.empty() && st.back() < x) {
            st.pop_back();
            --drop;
        }
        st.push_back(x);
    }

    // 只取前 k 个
    if ((int)st.size() > k) {
        st.resize(k);
    }
    return st;
}

// 检查一行是否只包含数字和空白
bool isValidLine(const string& s) {
    for (char ch : s) {
        if (!isdigit((unsigned char)ch) && !isspace((unsigned char)ch)) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line1;
    if (!getline(cin, line1)) {
        cout << "error\n";
        return 0;
    }
    if (line1.empty() || !isValidLine(line1)) {
        cout << "error\n";
        return 0;
    }

    string line2;
    if (!getline(cin, line2)) {
        cout << "error\n";
        return 0;
    }
    if (line2.empty() || !isValidLine(line2)) {
        cout << "error\n";
        return 0;
    }

    // 解析子包 ID 列表
    stringstream ss(line1);
    vector<int> nums;
    int x;
    while (ss >> x) {
        nums.push_back(x);
    }

    // 解析 k
    int k;
    stringstream ss2(line2);
    if (!(ss2 >> k)) {
        cout << "error\n";
        return 0;
    }
    vector<int> ans = maxSubsequence(nums, k);

    // 输出
    for (int i = 0; i < (int)ans.size(); ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

题目内容

网络侧需要给手机发送一个码流，一个码流由多个子包组成。例如:码流 $3$ $4$ $5$ $6$，该码流中含有四个子包，子包 $ID$ 分别为 $3、4、5、6$ 。

给定一个整数数组 $nums$ 用于保存这条码流子包 $ID$ ，另有一个正整数 $k$ 需要找出长度为 $k$ 且优先级最高 的 子包 $ID$ 集合。

在子包 $ID$ 集合 $a$ 和子包 $ID$ 集合 $b$ 的 第一个不相同的位置上，如果 $a$ 中的数字大于于 $b$ 中对应的数字，那么我们称子包 $ID$ 集合 $a$ 比子包 $ID$ 集合 $b$ (相同长度下)优先级更高。

例如，$[2,5,8]$ 比 $[2,4,9]$ 优先级更高，在第一个不相同的位置，也就是第个位置上，$5$ 大于 $4$ 。

输入描述

先输入码流，包含多个用 $10$ 进制正整数表示的子包 $ID$ ，每个子包 $ID$ 之间用空格隔开，最大支持编号从 $0$ 开始的 $500$ 种不同的子包

再输入需要找出的优先级最高的子包长度

注:子包 $ID$ 的先后顺序不可变更，但可删除或者不删除中间的子包 $ID$

输出描述

最高优先级的子包 $ID$ 集合，每个子包 $ID$ 用空格隔开

样例1

输入

0x2 0x2
1

输出

error

说明

仅支持 $10$ 进制数，输入中带有字母，打印 $error$

样例2

输入

6 3 2 4 4 3 8 5
4

输出

6 4 8 5

说明

在所有可能的长度为 $4$ 的子包 $ID$ 集合中，$6$ $4$ $8$ $5$ 的优先级最高。

样例3

输入

5 7 4 8
2

输出

7 8

说明

在所有可能的长度为 $2$ 的子包 $ID$ 集合 $[5,7],[5,4],[5,8],[7,4],[7,8],[4,8]$ 中，$[7,8]$ 的优先级最高。

提示

第一行码流最大长度: $2000$

子包 $ID$ 范围: $0<=nums[i] < 500$

子包长度范围: $1<=k<=nums.length$

以上数字只考虑 $10$ 进制数，不考虑其他，输入内容中带有非数字或者其他错误时打印 $error$