【CSP CCF记录】202212-2第28次认证 训练计划

题目

样例1输入

10 5
0 0 0 0 0
1 2 3 2 10

样例1输出

1 1 1 1 1
10 9 8 9 1

样例1解释

五项科目间没有依赖关系，都可以从第 1 天就开始训练。

10天时间恰好可以完成所有科目的训练。其中科目 1 耗时仅 1天，所以最晚可以拖延到第 10 天再开始训练；而科目 5 耗时 10 天，必须从第 1 天就开始训练。

样例2输入

10 7
0 1 0 3 2 3 0
2 1 6 3 10 4 3

样例2输出

1 3 1 7 4 7 1

样例3输入

10 5
0 1 2 3 4
10 10 10 10 10

样例3输出

1 11 21 31 41

代码

运用到最早开始时间、最晚开始时间，这篇博文总结得很好：

【学习分享】通俗易懂！最早（晚）开始时间_最早开始时间-CSDN博客

省流版
1、关键路径上节点的最早和最晚时间都是相同的，不能调整否则项目将延期。
2、计算最早时间用正推迭代，当出现多条分支时，上一个最早时间+最长分支路径时间计算，否则时间不够用。
3、计算最晚时间用反向迭代，当出现多条分支时，后一个最晚时间-最长分支路径时间计算，否则时间不够用。

没有什么难度，主要是理解题意。具体思路见注释。

#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef struct{
	int pid,days,earlist=1,latest=366;//依赖科目编号，所需时间，最早开始时间，最晚开始时间 
	vector<int> sid;//记录被哪些科目依赖 
}Project;
Project p[110];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>p[i].pid;
		p[p[i].pid].sid.push_back(i); 
	 } 
	bool can=true;//判断能否参赛 
	for(int i=1;i<=m;i++)
	{
		cin>>p[i].days;
		if(p[i].pid==0)//如果该科目无依赖 
		{
			p[i].earlist=1;
		}else{
			p[i].earlist=p[p[i].pid].earlist+p[p[i].pid].days;
			int last= p[i].earlist+p[i].days-1;//计算该科目的最后一天 
			if(last>n)can=false;//不能参赛 
		} 
		cout<<p[i].earlist<<" ";
	 } 

	cout<<endl; 
	if(can==true){//如果可以参赛，再计算最晚开始时间 
	for(int i=m;i>0;i--)//依赖科目小于自己，所以从后往前算最晚时间 
	{
		if (p[i].sid.empty())//如果没有被别的科目依赖 
		{
			p[i].latest=n-p[i].days+1;
		}else
		{
			int temp=366;
			int sz=p[i].sid.size();
			for(int j=0;j<sz;j++)//遍历依赖自己的科目 
			{
				int k=p[p[i].sid[j]].latest-p[i].days;
				if(k<=temp)temp=k; //取时间最早的 
			}
			p[i].latest=temp;
		}
		
	}
	for(int i=1;i<=m;i++)
	{
		cout<<p[i].latest<<" ";	
	}
		
    }
	
	return 0;	
}

运行