【CSP】202212-2 训练计划

题目

问题背景
西西艾弗岛荒野求生大赛还有
天开幕！

问题描述
为了在大赛中取得好成绩，顿顿准备在
天时间内完成“短跑”、“高中物理”以及“核裂变技术”等总共
项科目的加强训练。其中第
项（
）科目编号为
，也可简称为科目
。已知科目
耗时
天，即如果从第
天开始训练科目
，那么第
天就是该项训练的最后一天。

大部分科目的训练可以同时进行，即顿顿在同一天内可以同时进行多项科目的训练，但部分科目之间也存在着依赖关系。如果科目
依赖科目
，那么只能在后者训练结束后，科目
才能开始训练。具体来说，如果科目
从第
天训练到第
天，那么科目
最早只能从第
天开始训练。还好，顿顿需要训练的
项科目依赖关系并不复杂，每项科目最多只依赖一项别的科目，且满足依赖科目的编号小于自己。那些没有任何依赖的科目，则可以从第
天就开始训练。

对于每一项科目，试计算：

1）最早开始时间：该科目最早可以于哪一天开始训练？

2）最晚开始时间：在不耽误参赛的前提下（
天内完成所有训练），该科目最晚可以从哪一天开始训练？

天内完成所有训练，即每一项科目训练的最后一天都要满足
。需要注意，顿顿如果不能在
天内完成全部
项科目的训练，就无法参加大赛。这种情况下也就不需要再计算“最晚开始时间”了。

输入格式
从标准输入读入数据。

输入共三行。

输入的第一行包含空格分隔的两个正整数
和
，分别表示距离大赛开幕的天数和训练科目的数量。

输入的第二行包含空格分隔的
个整数，其中第
个（
）整数
表示科目
依赖的科目编号，满足
；
表示科目
无依赖。

输入的第三行包含空格分隔的
个正整数，其中第
个（
）数
表示训练科目
所需天数，满足
。

输出格式
输出到标准输出中。

输出共一行或两行。

输出的第一行包含空格分隔的
个正整数，依次表示每项科目的最早开始时间。

如果顿顿可以在
天内完成全部
项科目的训练，则继续输出第二行，否则输出到此为止。

输出的第二行包含空格分隔的
个正整数，依次表示每项科目的最晚开始时间。

代码

AC

#include<bits/stdc++.h>
using namespace std;struct
{int form=0;//先导课int day=0;//消耗int start=1;//最早int last_start=0;//最晚 
}course[105]; int main()
{int max=-1;int n,m;cin>>n>>m;for(int i=0;i<m;i++){cin>>course[i].form;}for(int i=0;i<m;i++){cin>>course[i].day;}for(int i=0;i<m;i++){if(course[i].form != 0){course[i].start = course[course[i].form-1].start+course[course[i].form-1].day;//该门课的最早开始时间为先导课最早结束时间}cout<<course[i].start<<" ";//输出最早开始时间 if((course[i].day+course[i].start)>max)//判断是否能上完课 max=course[i].day+course[i].start-1;		}if(max<=n)//能上就输出 {cout<<endl;for(int i=m-1;i>=0;i--){if(course[i].last_start==0)course[i].last_start=n-course[i].day+1;if(course[i].form != 0){int temp = course[i].last_start-course[course[i].form-1].day ;if(course[course[i].form-1].last_start == 0){course[course[i].form-1].last_start = temp ;}else{course[course[i].form-1].last_start = min(temp,course[course[i].form-1].last_start);}}}for(int i=0;i<m;i++){cout<<course[i].last_start<<" ";}}return 0;
}/*
14 7
0 1 0 3 2 3 0
2 1 6 3 10 4 3
*//*
51 5
0 1 2 3 4
10 10 10 10 10*/