题目链接
题目描述
求解思路
-
模拟:
over
表示能否按时完成所有训练项目rely[i]
表示第i
个项目的依赖项目编号(每个项目最多有一个依赖项目)days[i]
用来记录第i
个项目完成需要的天数allDays[i]
表示加上该项目的所有前置依赖项(包含其依赖项目的依赖项目),完成该项目总共需要的天数lateDays[i]
表示要想完成第i
个项目以及将第i
个项目作为依赖的所有项目所需要花费的最大时间。
-
需要注意:
- 根据题目要求,每个项目最多依赖一个项目,但是每个项目可能会被多个项目依赖,因此我们在判断最晚开始时间时需要选择用时最长的依赖项目。
lateDays[i]
表示要想完成第i
个项目以及将第i
个项目作为依赖的所有项目所需要花费的最大时间。要计算最晚开始时间,计算 n − l a t e D a y s [ i ] + 1 n-lateDays[i]+1 n−lateDays[i]+1 即可。
实现代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n, m;
boolean over = true;
n = in.nextInt();
m = in.nextInt();
int[] rely = new int[m + 1];
int[] days = new int[m + 1];
int[] allDays = new int[m + 1];
int[] lateDays = new int[m + 1];
for (int i = 1; i <= m; i ++) {
rely[i] = in.nextInt();
}
for (int i = 1; i <= m; i ++) {
days[i] = in.nextInt();
allDays[i] = days[i];
// 如果第i个项目没有依赖项目
if (rely[i] == 0) {
System.out.print(1 + " ");
} else {
System.out.print((allDays[rely[i]] + 1) + " ");
// 如果当前项目加上其前面的依赖项目和已经不能按时完成
if (allDays[rely[i]] + allDays[i] > n) {
over = false;
}
// 更新将第i个项目完成所需时间
allDays[i] += allDays[rely[i]];
}
}
if (over) {
System.out.println();
// 因为每个项目的依赖项目都在其前面,所以倒序遍历
for (int i = m; i >= 1; i --) {
lateDays[i] += days[i];
// 如果第i个项目依赖了某一个项目
if (rely[i] != 0) {
// 更新被依赖项目所花费的时间。
// 这里需要注意,被依赖项目也可能会被其他项目依赖,所以选时间最长的那个
lateDays[rely[i]] = Math.max(lateDays[i], lateDays[rely[i]]);
}
}
for (int i = 1; i <= m; i ++) {
System.out.print((n - lateDays[i] + 1) + " ");
}
}
}
}
标签:202212,rely,依赖,Java,项目,int,lateDays,allDays,CSP
From: https://blog.csdn.net/dawn191228/article/details/141526958