一、题目描述
现在有n个容器服务,服务的启动可能有一定的依赖性(有些服务启动没有依赖),其次服务自身启动加载会消耗一些时间。
给你一个 nxn 的二维矩阵 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 进行集成测试。
四、Java算法源码
java">public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] nums = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
nums[i][j] = sc.nextInt();
}
}
int k = sc.nextInt();
//从第K个服务,对应到数组行数就是k-1
int time = needTime(nums, k - 1);
System.out.println(time);
}
//获取当前服务的需要等待的最少时间
public static int needTime(int[][] nums, int k) {
int n = nums[0].length;
int selfTime = nums[k][k];
int dependMaxTime = 0;
for (int i = 0; i < n; i++) {
if (nums[k][i] == 1 && i != k) {
int time = needTime(nums, i);
dependMaxTime = Math.max(dependMaxTime, time);
}
}
return selfTime + dependMaxTime;
}
五、效果展示
1、输入
3
5 0 0
1 5 0
0 1 5
3
2、输出
15
🏆本文收录于,华为OD机试(JAVA)(2022&2023)
本专栏包含了最新最全的2023年华为OD机试真题,有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新,每天在线答疑。