【秋招笔试】24-08-01-用友-秋招笔试题

大家好这里是清隆Coding ，一枚热爱算法的程序员

ACM金牌团队️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 秋招笔试题

感谢大家的订阅➕ 和 喜欢 和 手里的小花花

✨ 笔试合集传送们 -> 春秋招笔试合集

⌚️ 01.物流网络安全节点

问题描述

LYA 是一家大型物流公司的系统工程师。她正在设计一个新的物流网络优化系统。在这个系统中，有 个物流节点，每个节点代表一个城市或仓库。节点之间存在单向的物流通道，形成了一个复杂的网络结构。

LYA 需要找出所有的"安全节点"。一个节点被称为"安全节点"，当且仅当从该节点出发的所有可能路径最终都能到达终端节点（没有出边的节点）。换句话说，如果一个节点的所有可能下游路径都能到达终端节点，那么这个节点就是安全的。

请你帮助 LYA 设计一个算法，找出所有的安全节点，并按升序排列输出它们的编号。

输入格式

第一行输入一个正整数 ，表示物流网络中节点的数量。

接下来 行，每行描述一个节点的出边情况。第 行（）包含若干个整数，表示从节点 出发可以直接到达的节点编号。如果该行只有一个 ，则表示该节点是终端节点。

输出格式

输出一行，包含若干个用空格分隔的整数，表示所有安全节点的编号，要求按升序排列。

样例输入1

5
1 2 3 4
1 2
3 4
0 4
-1

样例输出1

4

样例解释

在这个例子中，只有节点 4 是安全的，因为它是唯一的终端节点。

样例输入2

7
1 2
2 3
5
0
5
-1
-1

样例输出2

2 4 5 6

样例解释

5 和 6 为终端节即为“安全节点”， 2 和4开始的所有下游节点最终都指向终端节点，按照升序排列最终结果为2，4，5，6

数据范围

• 每行输入的节点编号
• 输入保证是一个有效的有向图描述

题解

这道题乍一看可能有点复杂，但其实我们可以换一种思路来解决。

首先，我们需要换个角度思考这个问题。与其考虑从一个节点出发能否到达终点，不如反过来想：从终点开始，哪些节点可以到达它？这样一来，我们就把问题转化成了一个更容易处理的形式。

具体做法是这样的：

1. 把图倒过来看。原来是A指向B，现在变成B指向A。
2. 数一数每个节点往外指的箭头数量。
3. 找出没有往外指箭头的节点，这些就是原图中的终点，肯定是安全的。
4. 从这些安全节点出发，顺着反向的箭头走。每走到一个新节点，就把它的箭头数减一。
5. 如果某个节点的箭头数减到零了，说明它所有的"下游"节点都是安全的，那它自己也就安全了。

这个过程就像是剥洋葱，从外层一层层往里剥，直到剥不动为止。剥下来的每一层都是安全节点。

整个剥洋葱的过程也就是我们熟悉的拓扑排序。

这种方法的时间复杂度是 ，其中排序需要 ，图的遍历需要 。空间复杂度是 。

参考代码

• Python

from collections import deque

def find_safe(n, links):
    # 构建反向连接和出度计数
    back = [[] for _ in range(n)]
    out = [0] * n
    
    for src in range(n):
        for dst in links[src]:
            if dst != -1:
                back[dst].append(src)
                out[src] += 1
    
    # 初始化安全点集合和队列
    safe = set(i for i in range(n) if out[i] == 0)
    q = deque(safe)
    
    # BFS遍历
    while q:
        cur = q.popleft()
        for prev in back[cur]:
            out[prev] -= 1
            if out[prev] == 0:
                safe.add(prev)
                q.append(prev)
    
    # 返回排序后的安全点列表
    return sorted(safe)

# 读取输入
n = int(input())
links = []
for _ in range(n):
    line = list(map(int, input().split()))
    links.append(line if line != [-1] else [])

# 计算结果并输出
result = find_safe(n, links)
print(' '.join(map(str, result)))

• Java

import java.util.*;

public class Main {
    public static List<Integer> findSafe(int n, int[][] links) {
        // 构建反向连接和出度计数
        List<List<Integer>> back = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            back.add(new ArrayList<>());
        }
        int[] out = new int[n];

        for (int src = 0; src < n; src++) {
            for (int dst : links[src]) {
                if (dst != -1) {
                    back.get(dst).add(src);
                    out[src]++;
                }
            }
        }

        // 初始化安全点集合和队列
        Set<Integer> safe = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (out[i] == 0) {
                safe.add(i);
                q.offer(i);
            }
        }

        // BFS遍历
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int prev : back.get(cur)) {
                if (--out[prev] == 0) {
                    safe.add(prev);
                    q.offer(prev);
                }
            }
        }

        // 返回排序后的安全点列表
        List<Integer> result = new ArrayList<>(safe);
        Collections.sort(result);
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] links = new int[n][];

        scanner.nextLine(); // 消耗换行符
        for (int i = 0; i < n; i++) {
            String[] line = scanner.nextLine().split(" ");
            links[i] = new int[line.length];
            for (int j = 0; j < line.length; j++) {
                links[i][j] = Integer.parseInt(line[j]);
            }
        }

        List<Integer> result = findSafe(n, links);
        for (int node : result) {
            System.out.print(node + " ");
        }
    }
}

• Cpp

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

vector<int> findSafe(int n, vector<vector<int>>& links) {
    // 构建反向连接和出度计数
    vector<vector<int>> back(n);
    vector<int> out(n, 0);
    
    for (int src = 0; src < n; src++) {
        for (int dst : links[src]) {
            if (dst != -1) {
                back[dst].push_back(src);
                out[src]++;
            }
        }
    }
    
    // 初始化安全点集合和队列
    set<int> safe;
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (out[i] == 0) {
            safe.insert(i);
            q.push(i);
        }
    }
    
    // BFS遍历
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int prev : back[cur]) {
            if (--out[prev] == 0) {
                safe.insert(prev);
                q.push(prev);
            }
        }
    }
    
    // 返回排序后的安全点列表
    vector<int> result(safe.begin(), safe.end());
    sort(result.begin(), result.end());
    return result;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> links(n);
    
    for (int i = 0; i < n; i++) {
        int x;
        while (cin >> x && x != -1) {
            links[i].push_back(x);
        }
        if (links[i].empty()) {
            links[i].push_back(-1);
        }
    }
    
    vector<int> result = findSafe(n, links);
    for (int node : result) {
        cout << node << " ";
    }
    cout << endl;
    
    return 0;
}

02.卢小姐的魔法调配

问题描述

卢小姐是一位著名的魔药大师。她最近发明了一种新的魔法药剂，这种药剂有一个独特的特性：它的魔力可以被分成 份（），而最终的魔法效果等于这 份魔力的乘积。

魔法议会认为这种药剂可能过于强大，因此要求对其魔法效果设置一个上限。现在给你魔法效果的上限和卢小姐的药剂魔力值，请判断这种药剂的实际魔法效果是否会超出给定的上限。

输入格式

输入包含两个整数 和 ，用空格分隔。

其中 表示魔法效果的上限， 表示药剂的魔力值。

输出格式

输出一个字符串，为 true 或 false。

如果药剂的魔法效果超出上限，输出 true；否则输出 false。

样例输入

2920 22

样例输出

false

样例解释

对于魔力值 22，最优的分配方式是 3 + 3 + 3 + 3 + 3 + 3 + 4，得到的魔法效果为 3^6 * 4 = 2916。 这个值不超过给定的上限 2920，因此输出 false。

样例输入

1 2

样例输出

false

样例解释

魔力值为 2，只能分成 1 + 1，魔法效果为 1 * 1 = 1，不超过上限 1，因此输出 false。

样例输入

161 14

样例输出

true

样例解释

魔力值 14 的最优分配方式是 3 + 3 + 3 + 3 + 2，得到的魔法效果为 3 * 3 * 3 * 3 * 2 = 162。 这个值超过了给定的上限 161，因此输出 true。

题解

这个问题可以简化为：给定一个正整数（魔力值），如何将其拆分成至少两个正整数，使得这些正整数的乘积最大化，并判断这个最大乘积是否超过给定的上限。

关键思路如下：

1. 对于小于等于 4 的魔力值，我们有固定的拆分方式：

   • 2 拆分为 1+1，乘积为 1
   • 3 拆分为 1+2，乘积为 2
   • 4 拆分为 2+2，乘积为 4

2. 对于大于 4 的魔力值，最优的拆分策略是：

   • 尽可能多地拆出 3
   • 如果余 1，将一个 3 和这个 1 合并成 4
   • 如果余 2，保持不变

这个策略基于以下数学事实：

• 3×3 > 2×2×2
• 3×3 > 3×2×1

因此，使用 3 作为基本单位可以让乘积最大化。唯一的例外是 4，因为 2×2 > 3×1。

在实际实现时，我们可以使用一个 while 循环来模拟拆分过程：

1. 初始化乘积为 1。
2. 如果魔力值小于等于 4，直接返回固定的结果。
3. 对于大于 4 的魔力值，重复以下步骤：如果剩余魔力值大于 4，从中减去 3，并将乘积乘以 3。如果剩余魔力值等于 4，将乘积乘以 4，结束循环。如果剩余魔力值小于 4，将乘积乘以剩余值，结束循环。在每一步后，检查乘积是否已经超过上限，如果超过则立即返回 true。

这种方法的时间复杂度是 ，其中 是魔力值。

参考代码

• Python

def is_over_limit(limit, power):
    """
    判断给定魔力值能产生的最大魔法效果是否超过上限
    :param limit: 魔法效果上限
    :param power: 魔力值
    :return: 是否超过上限
    """
    if power <= 4:
        return [1, 1, 2, 4][power-1] > limit
    
    product = 1
    while power > 4:
        product *= 3
        power -= 3
        if product > limit:
            return True
    
    product *= power
    return product > limit

# 读取输入
limit, power = map(int, input().split())

# 计算结果并输出
result = is_over_limit(limit, power)
print(str(result).lower())

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long limit = scanner.nextLong();
        int power = scanner.nextInt();
        
        boolean result = isOverLimit(limit, power);
        System.out.println(result);
    }
    
    /**
     * 判断给定魔力值能产生的最大魔法效果是否超过上限
     * @param limit 魔法效果上限
     * @param power 魔力值
     * @return 是否超过上限
     */
    private static boolean isOverLimit(long limit, int power) {
        if (power <= 4) {
            return new long[]{1, 1, 2, 4}[power-1] > limit;
        }
        
        long product = 1;
        while (power > 4) {
            product *= 3;
            power -= 3;
            if (product > limit) {
                return true;
            }
        }
        
        product *= power;
        return product > limit;
    }
}

• Cpp

#include <iostream>

using namespace std;

/**
 * 判断给定魔力值能产生的最大魔法效果是否超过上限
 * @param limit 魔法效果上限
 * @param power 魔力值
 * @return 是否超过上限
 */
bool isOverLimit(long long limit, int power) {
    if (power <= 4) {
        int results[] = {1, 1, 2, 4};
        return results[power-1] > limit;
    }
    
    long long product = 1;
    while (power > 4) {
        product *= 3;
        power -= 3;
        if (product > limit) {
            return true;
        }
    }
    
    product *= power;
    return product > limit;
}

int main() {
    long long limit;
    int power;
    cin >> limit >> power;
    
    bool result = isOverLimit(limit, power);
    cout << (result ? "true" : "false") << endl;
    
    return 0;
}

03.LYA的音乐节目编排

问题描述

LYA 是一个音乐节目的制作人。她正在为一个新的音乐节目安排表演顺序。节目中有 个表演项目，每个项目有不同的表演时长，有些项目因为技术原因无法进行（用 表示）。为了保持节目的流畅性，LYA 可以在规定的范围内调整表演顺序，但每次调整都需要消耗相应的时间来重新布置舞台。

LYA 的目标是找到一个从节目开始到结束的表演顺序，使得总耗时（包括表演时间和舞台重置时间）最少。如果存在多个总耗时相同的顺序，她希望选择按项目编号更小的顺序。如果无法安排到最后一个项目，则视为无法完成节目。

输入格式

第一行包含一个正整数 ，表示表演项目的数量。

第二行包含 个整数 ，其中 表示第 个项目的表演时长（ 表示该项目无法进行）。

第三行包含一个正整数 ，表示每次调整顺序时最多可以跳过的项目数。

输出格式

输出一行，包含若干个用空格分隔的整数，表示最优的表演顺序（用项目的编号表示，编号从 1 开始）。如果无法完成节目，则输出空数组 []。

样例输入1

5
1 2 4 -1 2
2

样例输出1

1 3 5

样例解释

最优的表演顺序是第 1、3、5 个项目，总耗时为 1 + 4 + 2 = 7。

样例输入2

5
1 2 4 -1 2
1

样例输出2

[]

样例解释

无法安排到最后一个项目，则视为无法完成节目，输出 []

数据范围

题解

这个问题可以简化为：在一个数组中找到一条路径，使得路径上的数字和最小，同时满足一些特定的跳跃规则。

想象 LYA 正在玩一个特殊的跳房子游戏。地上画了一排格子，每个格子上写着一个数字（表演时长），有些格子是坏的（无法表演的项目）。LYA 需要从第一个格子开始，一直跳到最后一个格子，但她每次最多只能跳过 m 个格子。

解决这个问题的关键是使用动态规划。可以把它想象成 LYA 在每个格子上都留下了一个笔记，记录到达这个格子的最小总耗时。

我们考虑如下步骤：

1. 准备一个笔记本（数组），用来记录到达每个格子的最小耗时。
2. 从第一个格子开始，逐个填写笔记。
3. 对于每个格子，看看能不能从前面的格子跳过来，如果可以，就计算一下总耗时，并记下最小的那个。
4. 同时，记录下是从哪个格子跳过来的，这样最后就能回溯出整个路径。
5. 如果遇到坏格子（-1），就跳过不管。
6. 最后，从终点开始，按照记录的来源格子，一路回溯到起点，就得到了最优路径。

这个方法之所以有效，是因为它利用了问题的最优子结构特性。

到达每个格子的最优路径，一定是由到达之前某个格子的最优路径再加上一步得到的。

具体实现可以看以下的代码实现

时间复杂为 ，其中 是格子数， 是最大跳跃距离。

参考代码

• Python

def arrange_performance(n, times, max_step):
    """
    安排最优表演顺序
    :param n: 项目数量
    :param times: 各项目表演时长
    :param max_step: 最大调整步长
    :return: 最优表演顺序
    """
    # 初始化动态规划数组和路径记录
    dp = [floa