CCF- CSP 202212-2训练计划 详细思路 满分题解(结尾附自编测试用例)

CCF- CSP 202212-2训练计划 详细思路 满分题解

题目链接：CCF- CSP 202212-2训练计划

思路：

• 测试数据满足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数组值初始化为极大。

代码如下：

#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