现在有 个容器服务,服务的启动可能有一定的依赖性(有些服务启动没有依赖),其次服务自身启动加载会消耗一些时间。
给你一个 的二维矩阵 useTime,其中 useTime[i][i]=10
表示服务 自身启动加载需要消耗10s,useTime[i][j]=1 表示服务 启动依赖服务 启动完成,useTime[i][k]=0
,表示服务 启动不依赖服务
其实 。服务之间启动没有循环依赖(不会出现环),若想对任意一个服务i进行集成测试(服务i自身也需要加载),求最少需要等待多少时间。
第一行输入服务总量 ,之后的 行表示服务启动的依赖关系以及自身启动加载耗时
最后输入 表示计算需要等待多少时间后可以对服务 进行集成测试
其中
最少需要等待多少时间(s)后可以对服务 进行集成测试
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进行集成测试
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进行集成测试
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,4自身加载需要消耗2s,3s,4s,5s,所以3+4+5=12s(因为服务1和服务2可以同时启动),需等待12s后可以对服务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进行集成测试
在这道题目中,我们需要计算对指定服务 k 进行集成测试所需的最少等待时间。我们需要考虑服务 k 以及它所依赖的服务的启动加载时间。
本题解法的核心思路是:遍历服务 k 及其所有依赖服务,累加这些服务的启动加载时间,得到最少等待时间。题目的解法具有线性时间复杂度和空间复杂度,对于最大输入规模 n=100,算法的性能是可以接受的。
#include <stdio.h>
#include <stdlib.h>
int main() {
int n, k;
scanf("%d", &n);
int **useTime = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
useTime[i] = (int *)malloc(n * sizeof(int));
for (int j = 0; j < n; j++) {
scanf("%d", &useTime[i][j]);
}
}
scanf("%d", &k);
int waitingTime = 0;
k--; // Convert to zero-based index
while (k >= 0) {
waitingTime += useTime[k][k];
for (int i = 0; i < n; i++) {
if (useTime[k][i] == 1) {
k = i;
break;
} else {
k = -1;
}
}
}
printf("%d\n", waitingTime);
for (int i = 0; i < n; i++) {
free(useTime[i]);
}
free(useTime);
return 0;
}
#include <iostream>
#include <vector>
int main() {
int n, k;
std::cin >> n;
std::vector<std::vector<int>> useTime(n, std::vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
std::cin >> useTime[i][j];
}
}
std::cin >> k;
int waitingTime = 0;
k--; // Convert to zero-based index
while (k >= 0) {
waitingTime += useTime[k][k];
for (int i = 0; i < n; i++) {
if (useTime[k][i] == 1) {
k = i;
break;
} else {
k = -1;
}
}
}
std::cout << waitingTime << std::endl;
return 0;
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
* <br>Author: Amos
* <br>E-mail: amos@amoscloud.com
* <br>Date: 2023/3/2
* <br>Time: 6:27
* <br>Description:
*/
public class Main0225 {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int n = scanner.nextInt();
int[][] matrix = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt();
}
}
int k = scanner.nextInt();
System.out.println(solution(matrix, n, k));
}
}
public static int solution(int[][] matrix, int n, int k) {
HashMap<Integer, ArrayList<Integer>> pre = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
pre.putIfAbsent(i, new ArrayList<>());
if (matrix[i][j] == 1) {
pre.get(i).add(j);
}
}
}
return dfs(k - 1, pre, matrix);
}
public static int dfs(int k, HashMap<Integer, ArrayList<Integer>> pre, int[][] matrix) {
if (pre.get(k).size() == 0) {
return matrix[k][k];
}
int maxPreTime = -1;
for (Integer p : pre.get(k)) {
maxPreTime = Math.max(maxPreTime, dfs(p, pre, matrix));
}
return matrix[k][k] + maxPreTime;
}
}
def main():
n = int(input())
useTime = [list(map(int, input().split())) for _ in range(n)]
k = int(input())
waitingTime = 0
k -= 1 # Convert to zero-based index
while k >= 0:
waitingTime += useTime[k][k]
for i in range(n):
if useTime[k][i] == 1:
k = i
break
else:
k = -1
print(waitingTime)
if __name__ == "__main__":
main()
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
const input = [];
rl.on("line", function (line) {
input.push(line.trim());
}).on("close", function () {
const n = parseInt(input.shift());
const useTime = input.slice(0, n).map(line => line.split(" ").map(Number));
const k = parseInt(input[n]);
let waitingTime = 0;
let serviceIndex = k - 1; // Convert to zero-based index
while (serviceIndex >= 0) {
waitingTime += useTime[serviceIndex][serviceIndex];
let dependencyFound = false;
for (let i = 0; i < n; i++) {
if (useTime[serviceIndex][i] === 1) {
serviceIndex = i;
dependencyFound = true;
break;
}
}
if (!dependencyFound) {
serviceIndex = -1;
}
}
console.log(waitingTime);
});
package main
import (
"fmt"
)
func main() {
var n, k int
fmt.Scan(&n)
useTime := make([][]int, n)
for i := 0; i < n; i++ {
useTime[i] = make([]int, n)
for j := 0; j < n; j++ {
fmt.Scan(&useTime[i][j])
}
}
fmt.Scan(&k)
waitingTime := 0
k-- // Convert to zero-based index
for k >= 0 {
waitingTime += useTime[k][k]
found := false
for i := 0; i < n; i++ {
if useTime[k][i] == 1 {
k = i
found = true
break
}
}
if !found {
k = -1
}
}
fmt.Println(waitingTime)
}