题解

题目描述

在微服务部署发布时，通常需要部署所有的现网局点。局点的部署过程存在依赖关系，因为某些局点需要等其他的局点部署完成后，才能开始部署。另外这些局点由于网络或地理位置的原因，所花费的部署时间有可能是不同的。给定一个大小为 n 的数组 region 存储局点之间的部署依赖关系，其中 region[i] 是第 i 个局点的依赖局点，0 <= i < n，-1 <= region[i] < n，-1 表示第 i 个局点没有依赖局点，不需要等待其他局点部署完成才能开始。同时给定一个大小为 n 的数组 time，time[i] 表示部署第 i 个局点所耗费的时间。请返回部署完所有现网局点所耗费的时间。

输入描述

• 输入共 3 行
  • 首行是一个正整数 n，表示输入的局点数量
  • 第二行包含 n 个整数，以空格分离，表示为每个局点 region 父节点下标
  • 第三行包含 n 个整数，以空格分离，表示为每个局点部署的具体时间

输出描述

返回所有局点部署完成的时间。

样例

输入1

6
2 2 -1 2 2 2
3 7 2 1 5 4

输出1

9

输入2

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

输出2

11

题解思路

问题分析

该问题的核心是计算每个局点部署的最早完成时间，而每个局点的部署时间可能受到依赖局点的影响。我们可以将局点和其依赖关系看作一个有向图，其中每个局点是一个节点，依赖关系则是从某个节点指向其依赖的节点。任务的调度就相当于在有向图中遍历每个节点，并计算每个节点的完成时间。

解决思路

1. 依赖关系的建模：将每个局点的依赖关系构建成一个图。region[i] 表示第 i 个局点的父节点，如果 region[i] 为 -1，说明该局点没有父节点，可以立即部署。

2. 计算每个节点的最早完成时间：从每个节点出发，递归地计算其最早完成时间。节点的最早完成时间是自己部署时间加上所有依赖节点的最长部署时间。

3. 记忆化递归：为了避免重复计算同一节点的部署完成时间，使用记忆化方法将每个节点的计算结果缓存起来。

4. 返回结果：最后，遍历所有节点，找到最长的部署时间，即为所有局点的部署完成时间。

复杂度分析

• 时间复杂度：每个节点只会被访问一次，计算一个节点的部署时间的时间复杂度为 O(1)，因此总的时间复杂度为 O(n)，其中 n 是局点的数量。

• 空间复杂度：主要是用于存储每个节点的最早完成时间的 memo 数组，空间复杂度为 O(n)。

Python 实现

def deploy_time(n, region, time):
    # 记录每个局点的最早完成时间
    memo = [-1] * n

    # 计算某个节点的最早完成时间
    def dfs(node):
        # 如果已经计算过，直接返回结果
        if memo[node] != -1:
            return memo[node]
        
        # 如果没有父节点，直接返回自己的时间
        if region[node] == -1:
            memo[node] = time[node]
        else:
            # 如果有父节点，计算依赖节点的最大完成时间
            memo[node] = time[node] + dfs(region[node])
        
        return memo[node]

    # 计算所有节点的最早完成时间，返回最大值
    max_time = 0
    for i in range(n):
        max_time = max(max_time, dfs(i))
    
    return max_time

# 读取输入
n = int(input())  # 局点数量
region = list(map(int, input().split()))  # 依赖关系数组
time = list(map(int, input().split()))  # 部署时间数组

# 计算并输出结果
result = deploy_time(n, region, time)
print(result)

Java 实现

import java.util.Scanner;

public class Main {

    // 记录每个局点的最早完成时间
    public static int[] memo;
    
    // 计算某个节点的最早完成时间
    public static int dfs(int node, int[] region, int[] time) {
        // 如果已经计算过，直接返回结果
        if (memo[node] != -1) {
            return memo[node];
        }

        // 如果该节点没有父节点，返回它自己的时间
        if (region[node] == -1) {
            memo[node] = time[node];
        } else {
            // 如果有父节点，计算父节点的完成时间
            memo[node] = time[node] + dfs(region[node], region, time);
        }
        return memo[node];
    }

    // 主函数，计算所有节点的最早完成时间，返回最大值
    public static int deployTime(int n, int[] region, int[] time) {
        memo = new int[n];
        // 初始化memo数组为-1，表示未计算
        for (int i = 0; i < n; i++) {
            memo[i] = -1;
        }

        int maxTime = 0;
        // 计算所有节点的最早完成时间，返回最大值
        for (int i = 0; i < n; i++) {
            maxTime = Math.max(maxTime, dfs(i, region, time));
        }

        return maxTime;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 局点数量
        int[] region = new int[n];
        int[] time = new int[n];
        
        // 读取region数组
        for (int i = 0; i < n; i++) {
            region[i] = sc.nextInt();
        }
        
        // 读取time数组
        for (int i = 0; i < n; i++) {
            time[i] = sc.nextInt();
        }
        
        // 计算并输出结果
        System.out.println(deployTime(n, region, time));
    }
}

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 递归计算某个节点的最早完成时间
int dfs(int node, const vector<int>& region, const vector<int>& time, vector<int>& memo) {
    // 如果已经计算过，直接返回结果
    if (memo[node] != -1) return memo[node];

    // 如果该节点没有父节点，返回它自己的时间
    if (region[node] == -1) {
        memo[node] = time[node];
    } else {
        // 如果有父节点，计算父节点的完成时间
        memo[node] = time[node] + dfs(region[node], region, time, memo);
    }

    return memo[node];
}

// 计算所有节点的最早完成时间，返回最大值
int deployTime(int n, const vector<int>& region, const vector<int>& time) {
    vector<int> memo(n, -1);  // 初始化memo数组为-1，表示未计算
    int maxTime = 0;

    // 计算所有节点的最早完成时间，返回最大值
    for (int i = 0; i < n; i++) {
        maxTime = max(maxTime, dfs(i, region, time, memo));
    }

    return maxTime;
}

int main() {
    int n;
    cin >> n;  // 局点数量
    vector<int> region(n), time(n);

    // 读取region数组
    for (int i = 0; i < n; i++) {
        cin >> region[i];
    }

    // 读取time数组
    for (int i = 0; i < n; i++) {
        cin >> time[i];
    }

    // 计算并输出结果
    cout << deployTime(n, region, time) << endl;

    return 0;
}

题目内容

在微服务部署发布时，通常需要部署所有的现网局点。局点的部署过程存在依赖关系，因为某些局点需要等其他的局点部署完成后，才能开始部署。另外这些局点由于网络或地理位置的原因，所花费的部署时间有可能是不同的。给定一个大小为 $n$ 的数组 $region$ 存储局点之间的部署依赖关系，其中 $region[i]$ 是第 $i$ 个局点的依赖局点，$0<=i<n，-1<=region[i]<n$，$-1$ 表示第 $i$ 个局点没有依赖局点，不需要等待其他局点部署完成才能开始。同时给定一个大小为 $n$ 的数组 $time$，$time[i]$ 表示部署第 $i$ 个局点所耗费的时间(分钟),$0<=i<n,0<time[i] <= 1000$。请返回部署完所有现网局点所耗费的时间(分钟)。

输入描述

输入共 $3$ 行

首行是一个正整数 $n$ ，表示输入的局点数量

第二行包含 $n$ 个整数，以空格分离，表示为每个局点 $region$ 父节点下标

第三行包含 $n$ 个整数，以空格分离，表示为每个局点部署的具体时间

数据范围：$1<=n<=1000,-1<=region[i]<=999,0<time[i]<=1000$

输出描述

返回所有局点部署完成的时间

样例1

输入

6
2 2 -1 2 2 2 
3 7 2 1 5 4

输出

9

说明

当前存在 $6$ 个节点，节点 $2$ 是每个节点的父节点，第二行为每个节点的单独部署时间。

第一层节点 $2$ 部署时间最长为 $2$ ，第二层节点 $1$ 部署时间最长为 $7$ ，耗时最长的部署链路为 $2-》7$，最长部署时间为 $9$ ;在 $9$ 分钟内所有局点可部署完

样例2

输入

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

输出

11

说明

当前存在 $5$ 个节点，节点 $0$，$2$ 父节点为 $3$ ，节点 $1$ 为根节点，节点 $4$ 父节点为 $2$ ，第二行为每个节点的单独部署时间。最长部署链路为 $1-》3-》0$，最长部署时间为 $11$ 分钟