华为OD机试真题双机位C卷【微服务的集成测试】 C语言实现

微服务的集成测试

华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型

华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解

其它语言题解链接

华为OD机试双机位C卷 - 微服务的集成测试 (Python & C++ & JAVA & JS & GO)

题目描述

现在有n个容器服务，服务的启动可能有一定的依赖性（有些服务启动没有依赖），其次服务自身启动加载会消耗一些时间。

给你一个 n x n 的二维矩阵useTime，其中

• useTime[i][i]=10 表示服务i自身启动加载需要消耗10s
• useTime[i][j]= 1 表示服务i启动依赖服务j启动完成
• useTime[i][k]=0 表示服务i启动不依赖服务k

其实 0<= i，j，k < n。

服务之间启动没有循环依赖（不会出现环），若想对任意一个服务i进行集成测试（服务i自身也需要加载），求最少需要等待多少时间。

输入描述

第一行输入服务总量 n，
之后的 n 行表示服务启动的依赖关系以及自身启动加载耗时
最后输入 k 表示计算需要等待多少时间后可以对服务 k 进行集成测试

其中 1 <= k <=n，1<=n<=100

输出描述

最少需要等待多少时间(s)后可以对服务 k 进行集成测试

用例1

输入

3 5 0 0 1 5 0 0 1 5 3

输出

15

说明

服务3启动依赖服务2，服务2启动依赖服务1，由于服务1，2，3自身加载需要消耗5s，所以5+5+5=15，需要等待15s后可以对服务3进行集成测试

用例2

输入

3 5 0 0 1 10 1 1 0 11 2

输出

26

说明

服务2启动依赖服务1和服务3，服务3启动需要依赖服务1，服务1，2，3自身加载需要消耗5s，10s，11s，所以5+10+11=26s，需要等待26s后可以对服务2进行集成测试。

用例3

输入

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

输出

12

说明

服务3启动依赖服务1和服务2，服务4启动需要依赖服务1，2，3，服务1，2，3自身加载需要消耗2s,3s,4s,5s，所以3+4+5=12s（因为服务1和服务2可以同时启动），要等待12s后可以对服务4进行集成测试。

用例4

输入

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

输出

11

说明

服务3启动依赖服务1和服务2，服务4启动需要依赖服务1，2，服务5启动需要依赖服务3，5，服务1，2，3，4，5自身加载需要消耗1s,2s,3s,4s,5s，所以2+4+5=11s（因为服务1和服务2可以同时启动，服务3和服务4可以同时启动），要等待11s后可以对服务5进行集成测试。

题解

思路

本题采用DFS思路：

1. 从题目其实可以很容易分析出来一个容器的启动时间自身启动时间 + 所有依赖服务中最长启动时间.
2. 基于1的分析，结果就是k容器它所依赖服务的最长时间 + 它自身启动时间就是结果。求k容器所依赖服务的启动时间与求k容器启动时间问题本质是一样的。这道题就非常适合使用DFS算法解决。
3. 可以在普通DFS加入剪枝优化，一个服务器的启动时间如果之前被计算过，如果再次搜索计算可以直接返回之前缓存的时间。下述代码使用visited和needTime数组实现。

code

#include<stdio.h>#include<stdlib.h>constintN=100;intn,k,time=0;intstore[N][N];//每个服务器需要启动的时间，作为缓存，减少重复搜索intneedtime[N]={0};// 记录是否访问intvisited[N]={0};// 递归获取k的启动时间， 启动时间 = 自身启动时间 + 所有依赖服务中最长启动时间intdfs(intk){// 复用之前的缓存if(visited[k]==1)returnneedtime[k];// 依赖服务的最长时间intmax_time=0;for(inti=0;i<n;i++){if(i!=k&&store[k][i]==1){inttime=dfs(i);if(time>max_time){max_time=time;}}}needtime[k]=max_time+store[k][k];visited[k]=1;returnneedtime[k];}intmain(){scanf("%d",&n);for(inti=0;i<n;i++){for(intj=0;j<n;j++){scanf("%d",&store[i][j]);}}scanf("%d",&k);intresult=dfs(k-1);printf("%d",result);}