题目

样例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

代码

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

#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;	
}

运行