笔试时间：2023年9月6日 秋招

备注：第三题暂无题解

第一题

题目：设备按秩序组网的最大拓扑长度

在设备组网方法中，有一种按照一定秩序的组网方式，即设备的组网按照设备优先级顺序进行，最后组成一个线性拓扑。给定一组设备，设备包含组网优先级和时延，进行秩序组网后(按照优先级从小到大排序)，输出线性拓扑中时延累加和小于等于目标值delay的最长子拓扑的长度。

概念约束:

a)子拓扑指线性拓扑连续的一段；

b) 最长子拓扑指的是拓扑中的设备数量最多的子拓扑；

c) 累加和是子拓扑中每个设备的时延之和；

d)优先按照优先级升序排序，其次按照时延升序排序；

输入描述

第一行是一个数组，第一个数字是数组长度，后面跟的是设备优先级数组元素，用整数表示。数组长度范围是[1, 100000]，优先级范围是[1,100000]；

第二行是一个数组，第一个数字是数组长度，后面跟的是设备时延数组元素，用整数表示，和第一行一一对应，时延范用是[1, 100000]；

第三行是目标值。

输出描述

最长子拓扑长度，如果没有满足条件的，则返回0。

样例输入一

6 1 3 2 5 4 6

6 12 19 15 17 13 22

50

样例输出一

3

提示:

最长子拓扑12 15 19，因为其是满足条件的最长子拓扑，且和46最小，所以最长子拓扑是3。

排序后的数组:

12 3 4 5 6

12 15 19 13 17 22

样例输入二

4 1008 1005 1005 1000

4 32 33 33 25

16

样例输出二

0

提示:

没有满足条件的子拓扑。

排序后的数组:

1000 1005 1005 1008

25 33 33 32

参考题解

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

import java.util.*;

class Main {
    static class Pair {
        int X, Y;

        public Pair(int X, int Y) {
            this.X = X;
            this.Y = Y;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = 100004;
        Pair[] pa = new Pair[N];
        long[] s = new long[N];
        int n, d;

        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            pa[i] = new Pair(scanner.nextInt(), 0);
        }

        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            pa[i].Y = scanner.nextInt();
        }

        d = scanner.nextInt();
        Arrays.sort(pa, 1, n + 1, (a, b) -> Integer.compare(a.X, b.X));

        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + pa[i].Y;
        }

        int ans = 0;
        for (int r = 1, l = 0; r <= n; r++) {
            while (s[r] - s[l] > d) {
                l++;
            }
            ans = Math.max(ans, r - l);
        }

        System.out.println(ans);
    }
}

第二题

题目：套碗游戏

有一套塑料套碗的玩具，碗中间有个洞，可以从大到小套到一个固定在桌子的木棍上，对这些套碗编号1,2,...,n。我们把碗套到木棍后可以随时取出，但是取出的方式，只能是从木棍的上方取出，一次只能取出一个碗。那么就有可能会有多种套碗和取碗的顺序组合。现在问题是，给定套碗的个数，计算取碗的所有排列组合数，并且对于某一个给定的取碗顺序，确定是否可行。

输入描述

第一行：一个正整数，表示套碗的个数M,M的取值范围是[2,100]；

第二行：取碗的序列，用空格分隔。

输出描述

第一行: 总共有多少种取碗方式；

第二行: 取碗的序列是否可行，是输出1，否输出0。

样例输入一

2

1 2

样例输出一

2

提示:

共有如下2种取碗方式:

2 1

1 2

样例输入二

3

3 1 2

样例输出二

5

提示：

共有如下5种取碗方式:

3 2 1

1 2 3

2 1 3

1 3 2

2 3 1

参考题解

贪心模拟入栈出栈。

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

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    
    for (int