荣耀笔试荣耀笔试题 0409

笔试时间：2025年04月09日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目

给一个由n个正整数组成的数组，将它拆分为多个严格递减的子序列，输出通过拆分可以获得的最少的子序列的个数,并输出这些子序列。

说明:1.某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列，且该子序列是指从原序列第一个元素遍历到最后一个元素而形成的序列。2.严格递减，指的是数组元素n[i]<n[i-1]的话，即为递减，不能跳跃算递减元素。

输入描述

输入一个由逗号分隔的正整数字符串。备注：正整数取值范围1~2147483647

输出描述

输出子序列个数和子序列备注: 1.首行输出子序列个数，末尾换行 2.每行输出一个子序列，序列内数字用逗号分隔。

样例输入

7,3,6,2,5,1

样例输出

2

7,3,2,1

6,5

说明：

如下子序列个数和子序列不符合严格递减要求:

7,6,5

3,2,1

参考题解

思路与代码遍历原数组中的每个元素，根据每个子序列最后一个元素是否比当前元素大来决定将该元素放入哪个子序列；如果存在多个符合要求的子序列，则优先选择子序列中最后元素最小的一个；如果不存在符合要求的子序列，则新建一个子序列，最终输出所有子序列的个数和内容。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    getline(cin, s);

    // 解析输入
    vector<int> arr;
    stringstream ss(s);
    string token;
    while (getline(ss, token, ',')) {
        arr.push_back(stoi(token));
    }

    vector<vector<int>> subs;

    for (int x : arr) {
        int idx = -1;
        int mini = INT_MAX;
        for (int i = 0; i < subs.size(); i++) {
            if (subs[i].back() > x) {
                if (mini == INT_MAX || subs[i].back() < mini) {
                    mini = subs[i].back();
                    idx = i;
                }
            }
        }
        if (idx == -1) {
            subs.push_back({x});
        } else {
            subs[idx].push_back(x);
        }
    }

    cout << subs.size() << endl;
    for (auto& sub : subs) {
        for (int i = 0; i < sub.size(); i++) {
            if (i > 0) cout << ",";
            cout << sub[i];
        }
        cout << endl;
    }
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] tokens = s.split(",");
        int[] arr = Arrays.stream(tokens).mapToInt(Integer::parseInt).toArray();

        List<List<Integer>> subs = new ArrayList<>();

        for (int x : arr) {
            int idx = -1;
            int mini = Integer.MAX_VALUE;
            for (int i = 0; i < subs.size(); i++) {
                int last = subs.get(i).get(subs.get(i).size() - 1);
                if (last > x) {
                    if (mini == Integer.MAX_VALUE || last < mini) {
                        mini = last;
                        idx = i;
                    }
                }
            }
            if (idx == -1) {
                subs.add(new ArrayList<>(Arrays.asList(x)));
            } else {
                subs.get(idx).add(x);
            }
        }

        System.out.println(subs.size());
        for (List<Integer> sub : subs) {
            for (int i = 0; i < sub.size(); i++) {
                if (i > 0) System.out.print(",");
                System.out.print(sub.get(i));
            }
            System.out.println();
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

import sys
s = sys.stdin.read().strip()
arr = list(map(int, s.split(',')))
subs = []
for x in arr:
    idx = -1
    mini = None
    for i, sub in enumerate(subs):
        if sub[-1] > x:
            if mini is None or sub[-1] < mini:
                mini = sub[-1]
                idx = i
    if idx == -1:
        subs.append([x])
    else:
        subs[idx].append(x)
print(len(subs))
for sub in subs:
    print(','.join(map(str, sub)))

第二题

题目

桌面上有一行卡片(1...N)，每张卡片i上都有一个分数(Si)。现在进行一个抽卡的游戏，每次抽卡可以获得分数，获得的分数为卡片左右两边卡牌上的分数乘积。若一边没有卡片，则用1去乘，两边都没有卡片，则得分。例如卡片3 5 2中，抽取5可得2*3=6分，抽3或者2得5分。如果只有最后一张卡片，则抽走得1分。抽完的卡片后剩余的卡片将按照原来的顺序依次排列，即，1 2 3 4 5张卡牌抽走卡牌3后变为1 2 4 5排列。现给出N张卡牌分数的排列，求最高可以获得的分数。