CCF- CSP 202212-2训练计划 详细思路 满分题解
题目链接：CCF- CSP 202212-2训练计划
思路：文章来源：https://www.toymoban.com/news/detail-534104.html
- 测试数据满足
0<n<365,0<m<100，一般情况下不会超时，该题目大概率不是考察算法优化时间复杂度，重点应该放到算法实现上 - 对于最早开始时间，思路比较简单：如果当前科目没有依赖，则最早开始时间就为1；如果当前科目有依赖，则最早开始时间为
所依赖科目的最早开始时间+所依赖科目完成所需的时间,即first[i]=first[p[i]]+t[p[i]]; - 判断能够全部完成训练，需要记录最后一项科目的完成时间，如果该科目时间超过n，则无法完成所有训练，不需要输出最晚开始时间
- 对于最晚开始时间，必须明确一点：
最后一个科目完成时，恰好是最后一天，才能满足最晚开始时间的要求，所以，从最后一个项目往前开始遍历（题目中指出：每项科目最多只依赖一项别的科目，且满足依赖科目的编号小于自己），如果当前项目没有后继项目，则最晚开始时间只需要保证该科目可以按时完成，即last[i] = n-t[i]+1;如果当前科目有依赖，则需要对依赖项目的最晚开始时间进行更新 - 依赖项目的最晚开始时间需要满足所有后继项目按时完成，因此，需要在所有更新的值里面去最小值，即
last[p[i]]=min(last[p[i]],last[i]-t[p[i]]);，由于取最小值，所以开始需要将last数组值初始化为极大。
代码如下：文章来源地址https://www.toymoban.com/news/detail-534104.html
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 500;
int n,m;//n为天数，m为科数
int p[N],t[N];//p为依赖编号，t为训练天数
int first[N];//最早开始时间
int last[N];//最晚开始时间
int len;//记录完成所有科目所需的最长时间，用于判断是否需要输出最晚时间
int back[N];//记录第i个科目的后继科目
int main()
{
memset(last, 0x3f3f, sizeof(last));//初始化最晚开始时间
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>p[i];
back[p[i]]=i;//p[i]的后继节点为i
}
for(int i=1;i<=m;i++)
{
cin>>t[i];
}
for(int i=1;i<=m;i++)
{
if(!p[i])//如果当前科目没有依赖关系，最早开始时间为第1天
{
first[i]=1;
}
else//如果当前科目有依赖关系，最早开始时间为所依赖项目的最早开始时间+所依赖项目完成所需的时间
{
first[i]=first[p[i]]+t[p[i]];
}
len = max(len,first[i]+t[i]-1);
}
//输出最早时间
for(int i=1;i<=m;i++)
{
cout<<first[i]<<" ";
}
if(len<=n)
{
cout<<endl;
//最晚开始时间，从后开始遍历
for(int i=m;i>=1;i--)
{
//如果没有后继节点，则最晚开始时间只需要保证该科目可以按时完成
if(!back[i])
{
last[i] = n-t[i]+1;
}
//只需要用if结构，因为是向前遍历
if(p[i])
{
//从后往前更新最晚时间，由于需要保证所有科目能够顺利完成，需要取最小值
last[p[i]]=min(last[p[i]],last[i]-t[p[i]]);
}
}
//输出最晚时间
for(int i=1;i<=m;i++)
{
cout<<last[i]<<" ";
}
}
return 0;
}
//10 7
//0 1 0 3 2 3 0
//2 1 6 3 5 4 3
//1 3 1 7 4 7 1
//3 5 1 8 6 7 8
到了这里，关于CCF- CSP 202212-2训练计划 详细思路 满分题解(结尾附自编测试用例)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
