题解

题目大意

在某个“最强大脑”游戏中，选手需要处理一个整数序列。序列中的每个整数取值范围为 [1, 10]。选手需要从序列中去掉 K 个整数，保留 N - K 个整数，使得保留的整数按照原序列的顺序拼接起来后，形成的整数值最大。

思路

为了得到保留整数拼接后的最大值，我们需要确保高位的数字尽可能大。为此，可以采用以下策略：

1. 优先保留值为10的元素：由于10在拼接时相对于1-9的数字更具优势，优先保留它们可以增加最终拼接数的值。

2. 使用贪心算法结合栈：

   • 遍历整数序列，使用一个栈来存储保留的整数。
   • 当当前数字比栈顶数字更大，并且还可以移除数字时，移除栈顶数字以便当前更大的数字能够占据更高的位数。
   • 特别处理值为10的元素，确保它们被优先保留。

3. 处理剩余的移除次数：在遍历完所有数字后，如果仍有剩余的移除次数，则从栈顶移除相应数量的数字。

4. 拼接结果：将栈中的数字按照顺序拼接成最终的最大整数。

步骤

1. 输入读取：

   • 读取整数序列的长度 N。
   • 读取 N 个整数，存储在列表 numbers 中。
   • 读取需要移除的整数个数 K。

2. 初始化和预处理：

   • 计算需要保留的整数个数 keep_k = N - K。
   • 创建一个列表 value_indices，用于存储值为1到10的整数在序列中的索引位置。

3. 优先处理值为10的元素：

   • 如果值为10的元素数量大于或等于需要保留的整数个数 keep_k，则直接选择 keep_k 个10并输出结果。
   • 否则，选择所有值为10的元素，并标记这些元素为已选择。

4. 选择其他元素：

   • 使用栈 stack 和分段列表 result_segments 来选择剩余的整数。
   • 遍历序列中的每个整数：
     • 如果遇到值为10的元素，则将当前栈中的索引保存到 result_segments 并清空栈。
     • 对于非10的整数，比较当前整数与栈顶整数的大小，根据需要移除较小的整数，以尽可能构成更大的拼接数。

5. 处理剩余的移除次数：

   • 如果遍历结束后仍有移除次数 remove_remaining，则从最后一个分段开始，继续移除较小的整数，直到用完所有移除次数。

6. 标记最终选择的元素：

   • 将最终选择的所有索引标记为已选择。

7. 生成并输出结果：

   • 收集所有被选择的元素，并根据值是否为10，将其拼接成最终的结果字符串。
   • 输出结果。

python

def main():
    # 读取输入
    n = int(input())  # 序列的长度
    a = list(map(int, input().split()))  # 序列中的整数
    dd = int(input())  # 需要移除的整数个数
    original_k = dd  # 保存原始的K值
    k = n - dd  # 需要保留的整数个数

    # 创建g列表，用于存储每个值对应的索引 (1 到 10)
    g = [[] for _ in range(11)]
    for i in range(n):
        if 1 <= a[i] <= 10:
            g[a[i]].append(i)
        # 如果a[i]可能超过10，可以适当调整g的大小或处理方式

    # 如果值为10的元素数量 >= 需要保留的k，则选择k个10
    if len(g[10]) >= k:
        ans = "10" * k
        print(ans)
        return

    # 否则，选择所有值为10的元素，并选择剩余的k个元素
    # 标记所有值为10的元素
    vis = [0] * n
    for idx in g[10]:
        vis[idx] = 1

    # 设置k为原始的remove_k
    k = original_k
    res = []
    stc = []

    for i in range(n):
        if a[i] == 10:
            res.append(stc.copy())
            stc.clear()
            continue
        # 当栈不为空，且当前数字比栈顶数字更大，并且还有移除次数时，移除栈顶数字
        while stc and a[stc[-1]] < a[i] and k > 0:
            stc.pop()
            k -= 1
        stc.append(i)

    if stc:
        res.append(stc.copy())

    stc.clear()

    # 处理剩余的移除次数
    while k > 0 and res:
        b = res.pop()
        for w in b:
            # 同样的逻辑，比较并移除不优的数字
            while stc and a[stc[-1]] < a[w] and k > 0:
                stc.pop()
                k -= 1
            stc.append(w)
        # 如果仍有移除次数，继续移除栈顶元素
        while k > 0 and stc:
            stc.pop()
            k -= 1
        if k == 0 and stc:
            res.append(stc.copy())

    # 标记最终选择的元素
    while res:
        for idx in res.pop():
            vis[idx] = 1

    # 收集所有被选择的元素并拼接成结果字符串
    result = ""
    for i in range(n):
        if vis[i]:
            if a[i] == 10:
                result += "10"
            else:
                result += str(a[i])

    # 输出结果
    print(result)

if __name__ == "__main__":
    main()

c++

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 读取输入
    int n;
    cin >> n; // 序列的长度
    
    vector<int> a(n);
    for(int &num : a){
        cin >> num; // 序列中的整数
    }
    
    int dd;
    cin >> dd; // 需要移除的整数个数
    int original_k = dd; // 保存原始的K值
    int k = n - dd; // 需要保留的整数个数
    
    // 创建g列表，用于存储每个值对应的索引 (1 到 10)
    vector<vector<int>> g(11, vector<int>());
    for(int i = 0; i < n; i++){
        if(1 <= a[i] && a[i] <= 10){
            g[a[i]].push_back(i);
        }
        // 如果a[i]可能超过10，可以适当调整g的大小或处理方式
    }
    
    // 如果值为10的元素数量 >= 需要保留的k，则选择k个10
    if(g[10].size() >= (size_t)k){
        string ans = "";
        for(int i = 0; i < k; i++) ans += "10";
        cout << ans;
        return 0;
    }
    
    // 否则，选择所有值为10的元素，并选择剩余的k个元素
    // 标记所有值为10的元素
    vector<int> vis(n, 0);
    for(auto idx : g[10]){
        vis[idx] = 1;
    }
    
    // 设置k为原始的remove_k
    k = original_k;
    vector<vector<int>> res; // 用于存储分段的索引
    vector<int> stc; // 栈，用于存储当前选择的索引
    
    for(int i = 0; i < n; i++){
        if(a[i] == 10){
            res.push_back(stc); // 保存当前栈中的索引
            stc.clear(); // 清空栈
            continue;
        }
        // 当栈不为空，且当前数字比栈顶数字更大，并且还有移除次数时，移除栈顶数字
        while(!stc.empty() && a[stc.back()] < a[i] && k > 0){
            stc.pop_back();
            k--;
        }
        stc.push_back(i);
    }
    
    if(!stc.empty()){
        res.push_back(stc); // 保存剩余的栈
    }
    
    stc.clear();
    
    // 处理剩余的移除次数
    while(k > 0 && !res.empty()){
        vector<int> b = res.back();
        res.pop_back();
        for(auto w : b){
            // 同样的逻辑，比较并移除不优的数字
            while(!stc.empty() && a[stc.back()] < a[w] && k > 0){
                stc.pop_back();
                k--;
            }
            stc.push_back(w);
        }
        // 如果仍有移除次数，继续移除栈顶元素
        while(k > 0 && !stc.empty()){
            stc.pop_back();
            k--;
        }
        if(k == 0 && !stc.empty()){
            res.push_back(stc); // 保存当前栈
        }
    }
    
    // 标记最终选择的元素
    while(!res.empty()){
        vector<int> segment = res.back();
        res.pop_back();
        for(auto idx : segment){
            vis[idx] = 1;
        }
    }
    
    // 收集所有被选择的元素并拼接成结果字符串
    string result = "";
    for(int i = 0; i < n; i++){
        if(vis[i]){
            if(a[i] == 10){
                result += "10";
            }
            else{
                result += to_string(a[i]);
            }
        }
    }
    
    // 输出结果
    cout << result;
    
    return 0;
}

java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt(); // 序列的长度
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = scanner.nextInt(); // 序列中的整数
        }
        int dd = scanner.nextInt(); // 需要移除的整数个数
        int original_k = dd; // 保存原始的K值
        int k = n - dd; // 需要保留的整数个数
        
        // 创建g列表，用于存储每个值对应的索引 (1 到 10)
        List<List<Integer>> g = new ArrayList<>();
        for(int i = 0; i <= 10; i++) g.add(new ArrayList<>());
        for(int i = 0; i < n; i++){
            if(1 <= a[i] && a[i] <= 10){
                g.get(a[i]).add(i);
            }
            // 如果a[i]可能超过10，可以适当调整g的大小或处理方式
        }
        
        // 如果值为10的元素数量 >= 需要保留的k，则选择k个10
        if(g.get(10).size() >= k){
            StringBuilder ans = new StringBuilder();
            for(int i = 0; i < k; i++) ans.append("10");
            System.out.println(ans.toString());
            return;
        }
        
        // 否则，选择所有值为10的元素，并选择剩余的k个元素
        // 标记所有值为10的元素
        int[] vis = new int[n];
        for(int idx : g.get(10)){
            vis[idx] = 1;
        }
        
        // 设置k为原始的remove_k
        k = original_k;
        List<List<Integer>> res = new ArrayList<>(); // 用于存储分段的索引
        List<Integer> stc = new ArrayList<>(); // 栈，用于存储当前选择的索引
        
        for(int i = 0; i < n; i++){
            if(a[i] == 10){
                res.add(new ArrayList<>(stc)); // 保存当前栈中的索引
                stc.clear(); // 清空栈
                continue;
            }
            // 当栈不为空，且当前数字比栈顶数字更大，并且还有移除次数时，移除栈顶数字
            while(!stc.isEmpty() && a[stc.get(stc.size()-1)] < a[i] && k > 0){
                stc.remove(stc.size()-1);
                k--;
            }
            stc.add(i);
        }
        
        if(!stc.isEmpty()){
            res.add(new ArrayList<>(stc)); // 保存剩余的栈
        }
        
        stc.clear();
        
        // 处理剩余的移除次数
        while(k > 0 && !res.isEmpty()){
            List<Integer> b = res.get(res.size()-1);
            res.remove(res.size()-1);
            for(int w : b){
                // 同样的逻辑，比较并移除不优的数字
                while(!stc.isEmpty() && a[stc.get(stc.size()-1)] < a[w] && k > 0){
                    stc.remove(stc.size()-1);
                    k--;
                }
                stc.add(w);
            }
            // 如果仍有移除次数，继续移除栈顶元素
            while(k > 0 && !stc.isEmpty()){
                stc.remove(stc.size()-1);
                k--;
            }
            if(k == 0 && !stc.isEmpty()){
                res.add(new ArrayList<>(stc)); // 保存当前栈
            }
        }
        
        // 标记最终选择的元素
        while(!res.isEmpty()){
            List<Integer> segment = res.get(res.size()-1);
            res.remove(res.size()-1);
            for(int idx : segment){
                vis[idx] = 1;
            }
        }
        
        // 收集所有被选择的元素并拼接成结果字符串
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < n; i++){
            if(vis[i] == 1){
                if(a[i] == 10){
                    result.append("10");
                }
                else{
                    result.append(a[i]);
                }
            }
        }
        
        // 输出结果
        System.out.println(result.toString());
        
        scanner.close(); // 关闭扫描器
    }
}

题目内容

某最强大脑游戏要求：选手在一个整数序列中(整数取值为 $[1,10]$)，自行去掉 $K$ 个整数，得到一个新的整数序列，-使得整数序列左到右拼接起来后，得到的整数值最大。

那么假设你是优秀的选手，在给定这个整数序列之后，你能够得到的最大整数值是多少?

输入描述

输入分为三行:

第一行为一个整数 $N$ ，表示整数序列有 $N$ 个元素，其取值范围$[1,100000]$

第二行为 $N$ 个整数，空格分割，其整数取值范围 $[1,10]$

第三行为一个整数 $K$ ，表示去掉 $K$ 个整数，其整数范围 $[0,N)$

如:

4
3 6 9 4
2

输出描述

输出一个最大的整数值

94

样例1

输入

4
3 6 9 4
2

输出

94

说明

整数序列 $3,6,9,4$去掉两个整数，那么最优选择是可以去掉 $3$ 和 $6$ ，那么他能得到的最大整数值就是 $94$ 。

样例2

输入

4
3 6 10 4
2

输出

610

说明

整数序列 $3,6,10,4$ 去掉两个整数，那么最优选择是可以去掉 $3$ 和 $4$ ，那么他能得到的最大整数值就是 $610$ 。