AcWing 4892. 训练计划(参考已有题解,含注释,含举例)
原题链接
简单
作者:
大新芽子
,
2023-11-16 12:07:21
,
所有人可见
,
阅读 98
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int M = 110;
int p[M], t[M], n, m, tf[M], tl[M];
//p[i]表示当前项目的依赖项目,t[i]表示当前项目所需的完成时间;
//tf[i]表示当前项目的最早完成时间,tl[i]表示当前项目的最晚开始时间
int main(){
cin >> n >> m; //距离大赛开幕的天数和训练科目的数量
for(int i = 1; i <= m; i++){
cin >> p[i]; //表示科目i依赖的科目编号
}
for(int i = 1; i <= m; i ++){
cin >> t[i]; //表示训练科目i所需要的天数
}
int mx = 0;
for(int i = 1; i <= m; i++){
if(p[i] == 0){
tf[i] = 1;
}else{
tf[i] = tf[p[i]] + t[p[i]];
//题目保证依赖科目的编号小于自己 ,所以从前往后遍历时,该项目的依赖项目的最早完成时间肯定已经算出,更新就可以
mx = max(mx,tf[i] + t[i] - 1); //所有项目最早开始后的直到最后一个项目完成的时间
}
printf("%d ", tf[i]);
}
if(mx > n) return 0; //如果最早开始的时间开始后,全部项目完成的时间大于距离比赛的日子,没有最晚开始时间
cout << endl;
memset(tl, 0x3f, sizeof tl) ; //最大化数组
for(int i = m; i > 0; i --){ //从最后一个项目开始遍历,题目中保证依赖项目的编号小于自己,所以最后一个项目一定没有后继项目
if( tl[i] > n ) tl[i] = n - t[i] + 1; //如果当前项目的最晚开始时间没有赋值,先给定一个初始值,
if(p[i] != 0) tl[p[i]] = min(tl[p[i]], tl[i] - t[p[i]]); //如果有后继项目,则通过后继项目更新该项目的最晚开始时间
//当一个项目有多个后继项目时,必须要保证后继项目中时间最长的后继项目完成,所以当前项目的最晚完成时间选最小的
//tl[i] - t[p[i]]:后继项目最晚开始时间-当前项目完成所需要的天数 = 当前项目的最晚开始时间
}
for(int i = 1; i <= m; i ++){
printf("%d ", tl[i]);
}
return 0;
}