华为校招机试 - 云上故障逃生（20240417）

男娘i 2024-04-26 03:38 90阅读 0赞

#### 在线OJ测试 ####

[题目详情 - 云上故障逃生 - HydroOJ][- _ - HydroOJ]

#### 题目描述 ####

在云上多个业务节点之间选择最快的逃生节点集，并考虑每个节点的剩余业务容量。

有一个网络时延表，表示每个节点到其他节点的通信延迟，还有一个剩余业务容量表，表示每个节点的剩余业务容量。

在一个节点故障时，需要选择一个或多个逃生节点，确保逃生路径的时延最小，并且"逃生节点集"各节点剩余容量的总和足够容纳故障节点的业务量，当故障节点与多个节点最短距离相同，优先选择编号较小的节点容灾。

如果"逃生节点集"中多个节点最短距离相同时按编号从小到大的顺序排列。

#### 输入描述 ####

*  第 1 行：n，表示云上业务节点数， 2 ≤ n ≤ 10000，节点编号从 0 开始，依次递增
 *  第 2 到 1 + n 行：表示业务节点间的网络时延矩阵表 delayMatrix，delayMatrix\[i\]\[j\] 表示节点 i 到节点 j 的通信时延

1.  如果节点 i 和节点 j 之间没有直接相连的边，则 delayMatrix\[i\]\[j\] 为 -1，第 i 个节点和它自己也没有边，所以 delayMatrix\[i\]\[i\] 为 -1
2.  节点间有边时延范围为 1 ≤ delayMatrix\[i\]\[j\] ≤ 1000，矩阵元素间使用空格分割，输入保证 delayMatrix\[i\]\[j\] == delayMatrix\[j\]\[i\]

*  第 2 + n 行：表示各业务节点的剩余容量表 remainingCapacity，其中 remainingCapacity\[i\] 表示节点 i 的剩余业务容量，业务量的范围 1 ≤ remainingCapacity\[i\] ≤ 100，数组元素间使用空格分割
 *  第 3 + n 行：表示故障业务节点编号 faultyNode，表示发生故障的节点，取值范围为 0 ≤ faultyNode ≤ n−1
 *  第 4 + n 行：表示受损业务节点需要迁移的业务量，受损业务量的范围 (0−1000\]

#### 输出描述 ####

返回符合条件的逃生路径节点编号列表（以单空格间隔），

当所有节点都不够故障节点业务容灾的时候输出所有容灾节点。

#### 用例 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">4<br> -1 5 -1 8<br> 5 -1 1 3<br> -1 1 -1 4<br> 8 3 4 -1<br> 10 20 15 25<br> 2<br> 12</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;"> <p>根据输入的矩阵画出如下图：</p> <p><img alt="" height="370" src="https://img-blog.csdnimg.cn/direct/3b0faf0f75b04ba99fc1f3d1225b2451.png" width="429"></p> <p>在给定的测试用例中，假设节点2发生故障，需要迁移业务量为12。节点2到其它节点的最短路径如下：</p> <p><img alt="" height="109" src="https://img-blog.csdnimg.cn/direct/1dc5c74f06734add999357165db47bd2.png" width="323"></p> <p>离故障节点2时延排序为1,3,0，故障节点要转移的业务量为12，而节点1的可容灾余量为20，足够容纳故障节点2的受灾业务，所以该测试用例的期望输出是 1。</p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">4<br> -1 5 -1 8<br> 5 -1 1 3<br> -1 1 -1 4<br> 8 3 4 -1<br> 10 20 15 25<br> 2<br> 50</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">1&nbsp;3&nbsp;0</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;"> <p>根据输入的矩阵画出如下图：</p> <p><img alt="" height="361" src="https://img-blog.csdnimg.cn/direct/a46989f195f748f688899f374cb99038.png" width="407"></p> <p>在给定的测试用例中，假设节点2发生故障，需要迁移业务量为50。节点2到其它节点的最短路径如下：</p> <p><img alt="" height="109" src="https://img-blog.csdnimg.cn/direct/1dc5c74f06734add999357165db47bd2.png" width="323"></p> <p>离故障节点2时延排序为1,3,0，故障节点要转移的业务量为50，而节点1的可容灾余量为20，不够容纳故障节点2的受灾业务50，所以还需找离节点2次近的节点3，节点3的可容灾余量为25，节点1的可容灾余量20和节点3的可容灾余量25的总和为45小于故障量50，需要增加0节点来容灾，，节点0的容灾余量为10，节点1,3,0总容灾余量为55，大于受灾节点的业务量50，所以该测试用例的期望输出是 1 3 0。</p> </td> 
  </tr> 
 </tbody> 
</table>

#### 题目解析 ####

本题题目描述很复杂，但是根据用例说明来看，本题就是需要我们求解：从faultNode出发，到其余节点的最短路，即单源最短路问题。

单源最短路问题的求解，我们可以使用dijkstra算法，关于dijkstra算法可以看下：

[LeetCode - 743 网络延迟时间（Java & JS & Python）\_有 n 个网络节点,标记为 1 到 n。 给你一个列表 times,表示信号经过 有向 边的传-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/qfc\_128220/article/details/127680161?spm=1001.2014.3001.5501][LeetCode - 743 _Java _ JS _ Python_ n _ 1 _ n_ _ times_ _ _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_qfc_128220_article_details_127680161_spm_1001.2014.3001.5501]

理解上面题目后，我们就可以发现，dijkstra算法其实就是：bfs + 贪心。

> 即每次bfs队列出队的点，都要是bfs队列所有点中的最短路点，即每次都从最短路点继续探索下一步

而bfs的队列由于每轮出队前都要进行比较，取出最短路点，因此我们可以使用优先队列进行优化，降低时间复杂度（对于JS，C而言，没有内置的优先队列，因此为了减轻代码量，可以继续有序数组）

本题变动的地方在于，bfs队列每次选择最短路点时：

*  如果队列中有多个节点都是最短路的（距离故障节点时延相同且最短），我们要优先选则走编号较小的节点

故障节点 i 可以选择多个节点 j1~jm 进行逃生

我们要优先确保：

*  max(delayMatrix\[i\]\[j1\], delayMatrix\[i\]\[j2\], .., delayMatrix\[i\]\[jm\]) 最小，即最大时延节点的时延最小

> 只要每轮选择对应轮次的最短路点，即可保证选择的逃生节点集中的最大时延节点的时延最小

其次确保：

*  sum(remainCapacity\[j1\], remainCapacity\[j2\], ...，remainCapacity\[jm\]) >= 受损业务节点需要迁移的业务量

> 记录每轮选择的最短路节点，统计已选择节点的remainCapacity之和，当其大于等于受损业务节点需要迁移的业务量，即可停止Dijkstra流程。

最终，我们需要打印逃生节点集的节点编号，打印顺序应该是：距离故障节点的时延越小越靠前，时延相同的，编号越小越靠前。

其实这个打印顺序就是Dijkstra的最短路节点的探索顺序。

#### JS算法源码 ####

#### Java算法源码 ####

import java.util.*;
    
    public class Main {
        static int n;
        static int[][] delayMatrix;
        static int[] remainingCapacity;
        static int faultyNode;
        static int faultyNode_volume;
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
    
            // 云上业务节点数
            n = sc.nextInt();
    
            // delayMatrix[i][j]表示节点i到节点j的通信时延
            delayMatrix = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    delayMatrix[i][j] = sc.nextInt();
                }
            }
    
            // 剩余容量表
            remainingCapacity = new int[n];
            for (int i = 0; i < n; i++) {
                remainingCapacity[i] = sc.nextInt();
            }
    
            // 发生故障的节点
            faultyNode = sc.nextInt();
    
            // 受损业务节点需要迁移的业务量
            faultyNode_volume = sc.nextInt();
    
            System.out.println(dijkstra());
        }
    
        public static String dijkstra() {
            // visited[i]==true表示:节点i已找到最短路径
            boolean[] visited = new boolean[n];
    
            // dist[j] 表示故障节点faultyNode到节点j的最短时延
            int[] dist = new int[n];
            // 初始时，假设故障节点无法到达其他节点，即时延无限大
            Arrays.fill(dist, Integer.MAX_VALUE);
            // 故障节点到自身无时延
            dist[faultyNode] = 0;
    
            // 优先队列记录的元素是数组[节点编号, 距离源点的时延], 出队时，时延越短越优先, 时延相同时,节点编号越小越优先
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] != b[1] ? a[1] - b[1] : a[0] - b[0]);
            // 初始时从故障节点出发
            pq.add(new int[]{faultyNode, 0});
    
            // sj记录题解
            StringJoiner sj = new StringJoiner(" ");
            // 剩余的未被迁移的受损业务量
            int remain_volume = faultyNode_volume;
    
            // 如果还有节点可探索，且还有剩余的未被迁移的受损业务量
            while (!pq.isEmpty() && remain_volume > 0) {
                // 上一次的最短路终点i，作为下一步的起点
                int i = pq.poll()[0];
    
                // 如果节点i在之前已经找到了最短时延，那么此时出队的i必然不是最短时延，因此可以忽略
                if (visited[i]) continue;
                // 否则此时出队的i是最短时延，记录找到了节点i到源点的最短时延
                visited[i] = true;
    
                // 如果 i 不是故障节点，那么就可以容纳remainingCapacity[i]大小的受灾业务
                if (i != faultyNode) {
                    // 剩余的未被迁移的受损业务量减少remainingCapacity[i]
                    remain_volume -= remainingCapacity[i];
                    sj.add(i + "");
                }
    
                for (int j = 0; j < n; j++) {
                    if (delayMatrix[i][j] != -1) {
                        // newDist：故障节点到 j 的时延
                        int newDist = dist[i] + delayMatrix[i][j];
    
                        // 如果newDist更短，则
                        if (dist[j] > newDist) {
                            // 更新故障节点到 j 的最短时延dist[j]为newDist
                            dist[j] = newDist;
                            // j 加入下一轮最短路起点的比较
                            pq.add(new int[]{j, dist[j]});
                        }
                    }
                }
            }
    
            return sj.toString();
        }
    }

#### Python算法源码 ####

import heapq
    import sys
    
    # 输入获取
    n = int(input())
    delayMatrix = [list(map(int, input().split())) for _ in range(n)]
    remainCapacity = list(map(int, input().split()))
    faultNode = int(input())
    faultNode_volume = int(input())
    
    
    # 算法入口
    def dijkstra():
        # visited[i]==true表示:节点i已找到最短路径
        visited = [False] * n
    
        # dist[j] 表示故障节点faultyNode到节点j的最短时延, 初始时，假设故障节点无法到达其他节点，即时延无限大
        dist = [sys.maxsize for i in range(n)]
        # 故障节点到自身无时延
        dist[faultNode] = 0
    
        # 优先队列, dist时延越短越优先,dist时延相同时,节点编号越小越优先
        pq = []
        # 初始时从故障节点出发
        heapq.heappush(pq, (dist[faultNode], faultNode))
    
        # 记录题解
        ans = []
        # 剩余的未被迁移的受损业务量
        remain_volume = faultNode_volume
    
        # 如果还有节点可探索，且还有剩余的未被迁移的受损业务量
        while len(pq) > 0 and remain_volume > 0:
            # 上一次的最短路终点i，作为下一步的起点
            _, i = heapq.heappop(pq)
    
            # 如果节点i在之前已经找到了最短时延，那么此时出队的i必然不是最短时延，因此可以忽略
            if visited[i]:
                continue
            
            # 否则此时出队的i是最短时延，记录找到了节点i到源点的最短时延
            visited[i] = True
    
            # 如果 i 不是故障节点，那么就可以容纳remainingCapacity[i]大小的受灾业务
            if i != faultNode:
                remain_volume -= remainCapacity[i]
                ans.append(i)
    
            for j in range(n):
                if delayMatrix[i][j] != -1:
                    newDist = dist[i] + delayMatrix[i][j]
    
                    # 如果newDist更短，则
                    if dist[j] > newDist:
                        # 更新故障节点到 j 的最短时延dist[j]为newDist
                        dist[j] = newDist
                        # j 加入下一轮最短路起点的比较
                        heapq.heappush(pq, (dist[j], j))
    
        return " ".join(map(str, ans))
    
    
    # 算法调用
    print(dijkstra())

#### C算法源码 ####

#include <stdio.h>
    #include <limits.h>
    #include <stdlib.h>
    
    #define MAX_N 10000
    
    int cmp(const void *a, const void *b) {
        int *A = (int *) a;
        int *B = (int *) b;
        return A[1] != B[1] ? B[1] - A[1] : B[0] - A[0];
    }
    
    void dijkstra(int n, int delayMatrix[n][n], const int remainCapacity[], int faultNode, int faultNode_volume) {
        // visited[i]==1 表示:节点i已找到最短路径
        int visited[n];
        // dist[i] 表示故障节点faultyNode到节点i的最短时延,
        int dist[n];
    
        // 初始时，假设故障节点无法到达其他节点，即时延无限大, 且所有节点都未找到最短路
        for (int i = 0; i < n; i++) {
            visited[i] = 0;
            dist[i] = INT_MAX;
        }
    
        // 故障节点到自身无时延
        dist[faultNode] = 0;
    
        // 优先队列记录的元素是数组[节点编号, 距离源点的时延], 出队时，时延越短越优先, 时延相同时,节点编号越小越优先
        int pq[MAX_N][2];
        int pq_size = 0;
    
        // 初始时从故障节点出发
        pq[pq_size][0] = faultNode; // 节点编号
        pq[pq_size][1] = 0; // 节点距离源点的时延
        pq_size++;
    
        // 如果还有节点可探索，且还有剩余的未被迁移的受损业务量
        while (pq_size > 0 && faultNode_volume > 0) {
            // 上一次的最短路终点i，作为下一步的起点
            int i = pq[--pq_size][0];
    
            // 如果节点i在之前已经找到了最短时延，那么此时出队的i必然不是最短时延，因此可以忽略
            if (visited[i]) continue;
            // 否则此时出队的i是最短时延，记录找到了节点i到源点的最短时延
            visited[i] = 1;
    
            // 如果 i 不是故障节点，那么就可以容纳remainingCapacity[i]大小的受灾业务
            if (i != faultNode) {
                // 剩余的未被迁移的受损业务量减少remainingCapacity[i]
                faultNode_volume -= remainCapacity[i];
                printf("%d ", i);
            }
    
            for (int j = 0; j < n; j++) {
                // i -> j 的时延为delayMatrix[i][j]
                if (delayMatrix[i][j] != -1) {
                    // newDist：故障节点到 j 的时延
                    int newDist = dist[i] + delayMatrix[i][j];
    
                    // 如果newDist更短，则
                    if (dist[j] > newDist) {
                        // 更新故障节点到 j 的最短时延dist[j]为newDist
                        dist[j] = newDist;
                        // j 加入下一轮最短路起点的比较
                        pq[pq_size][0] = j;
                        pq[pq_size][1] = dist[j];
                        pq_size++;
                        // dist时延越短越优先,dist时延相同时,节点编号越小越优先
                        // pq有序数组尾部是最优先的，因此cmp降序
                        qsort(pq, pq_size, sizeof(pq[0]), cmp);
                    }
                }
            }
        }
    
    }
    
    int main() {
        int n;
        scanf("%d", &n);
    
        int delayMatrix[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &delayMatrix[i][j]);
            }
        }
    
        int remainCapacity[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &remainCapacity[i]);
        }
    
        int faultNode;
        scanf("%d", &faultNode);
    
        int faultNode_volume;
        scanf("%d", &faultNode_volume);
    
        dijkstra(n, delayMatrix, remainCapacity, faultNode, faultNode_volume);
    
        return 0;
    }

#### C++算法源码 ####

#include <bits/stdc++.h>
    
    using namespace std;
    
    int n;
    vector<vector<int>> delayMatrix;
    vector<int> remainCapacity;
    int faultNode;
    int faultNode_volume;
    
    void dijkstra() {
        // visited[i]==true表示:节点i已找到最短路径
        vector<bool> visited(n, false);
    
        // dist[j] 表示故障节点faultyNode到节点j的最短时延, 初始时，假设故障节点无法到达其他节点，即时延无限大
        vector<int> dist(n, INT_MAX);
        // 故障节点到自身无时延
        dist[faultNode] = 0;
    
        // 优先队列记录的元素是数组[节点编号, 距离源点的时延], 出队时，时延越短越优先, 时延相同时,节点编号越小越优先
        auto cmp = [](const int *a, const int *b) {
            return a[1] != b[1] ? a[1] > b[1] : a[0] > b[0];
        };
        priority_queue<int, vector<int *>, decltype(cmp)> pq(cmp);
    
        // 初始时从故障节点出发
        pq.push(new int[]{faultNode, 0});
    
        // 剩余的未被迁移的受损业务量
        int remain_volume = faultNode_volume;
    
        // 如果还有节点可探索，且还有剩余的未被迁移的受损业务量
        while (!pq.empty() && remain_volume > 0) {
            // 上一次的最短路终点i，作为下一步的起点
            int i = pq.top()[0];
            pq.pop();
    
            // 如果节点i在之前已经找到了最短时延，那么此时出队的i必然不是最短时延，因此可以忽略
            if (visited[i]) continue;
            // 否则此时出队的i是最短时延，记录找到了节点i到源点的最短时延
            visited[i] = true;
    
            // 如果 i 不是故障节点，那么就可以容纳remainingCapacity[i]大小的受灾业务
            if (i != faultNode) {
                // 剩余的未被迁移的受损业务量减少remainingCapacity[i]
                remain_volume -= remainCapacity[i];
                cout << i << " ";
            }
    
            for (int j = 0; j < n; j++) {
                if (delayMatrix[i][j] != -1) {
                    // newDist：故障节点到 j 的时延
                    int newDist = dist[i] + delayMatrix[i][j];
    
                    // 如果newDist更短，则
                    if (dist[j] > newDist) {
                        // 更新故障节点到 j 的最短时延dist[j]为newDist
                        dist[j] = newDist;
                        // j 加入下一轮最短路起点的比较
                        pq.push(new int[]{j, dist[j]});
                    }
                }
            }
        }
    }
    
    int main() {
        cin >> n;
    
        delayMatrix = vector<vector<int>>(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> delayMatrix[i][j];
            }
        }
    
        remainCapacity = vector<int>(n);
        for (int i = 0; i < n; i++) {
            cin >> remainCapacity[i];
        }
    
        cin >> faultNode;
    
        cin >> faultNode_volume;
    
        dijkstra();
    
        return 0;
    }

[- _ - HydroOJ]: https://hydro.ac/d/HWOCR/p/OCR032
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[LeetCode - 743 _Java _ JS _ Python_ n _ 1 _ n_ _ times_ _ _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_qfc_128220_article_details_127680161_spm_1001.2014.3001.5501]: https://blog.csdn.net/qfc_128220/article/details/127680161?spm=1001.2014.3001.5501