CSP-202212-2-训练计划

解题思路

1. 输入和初始化：

   • 首先，代码从输入中获取项目的截止日期和项目数量。
   • 然后，它初始化一个项目列表，每个项目都有其依赖项、被依赖的项目集合、完成时间、总完成时间（包括依赖链）、最早和最晚开始时间。

2. 建立依赖关系：

   • 通过输入确定每个项目的依赖项目。如果一个项目依赖另一个项目，那么被依赖的项目的集合会更新，加入依赖它的项目。
   • 同时记录每个项目的直接完成时间。

3. 计算总完成时间（Sumtime）：

   • 从后向前遍历项目列表，如果一个项目有依赖（即，它不是独立的），则更新它依赖的项目的总完成时间为：当前项目的总完成时间加上依赖项目的直接完成时间的最大值。

4. 计算最迟开始时间：

   • 遍历项目列表，每个项目的最迟开始时间等于截止日期减去该项目的总完成时间加一。
   • 如果计算出的最迟开始时间小于或等于0，则标记flag，表示存在项目不能在截止日期前完成。

5. 计算最早开始时间：

   • 遍历项目列表，如果一个项目没有依赖（即其依赖项目编号为0），其最早开始时间为1。
   • 如果项目有依赖，其最早开始时间为依赖项目的最早开始时间加上依赖项目的完成时间。

6. 输出：

   • 最后，代码输出每个项目的最早和最晚开始时间。如果flag被设置（意味着有项目无法按时完成），则只输出最早开始时间。

完整代码

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

struct MyProject
{
    int dependProject; // 依赖哪一个项目，0是无依赖项目
    vector<int>dependSet; // 被依赖的项目集合
    int timeSpend; // 完成本任务所需要的时间
    int Sumtime; // 完成任务（依赖链）所需时间
    int earliestStartTime; // 最早开始时间
    int latestStartTime; //最迟开始时间
};


int main() {
    int deadline, projectNum;
    cin >> deadline >> projectNum;
    vector<MyProject>projectList(projectNum + 1);

    // 输入依赖 
    for (int i = 1; i <= projectNum; i++)
    {
        cin >> projectList[i].dependProject;
        projectList[projectList[i].dependProject].dependSet.push_back(i);
    }
    // 输入单个任务所消耗时间
    for (int i = 1; i <= projectNum; i++)
    {
        cin >> projectList[i].timeSpend;
        projectList[i].Sumtime = projectList[i].timeSpend;
    }

    // 计算每个任务的Sumtime
    for (int i = projectNum; i >= 1; i--)
    {
        if (projectList[i].dependProject != 0) // 有依赖-找到最长依赖时间
        {
            projectList[projectList[i].dependProject].Sumtime = max(projectList[projectList[i].dependProject].Sumtime,
                projectList[projectList[i].dependProject].timeSpend + projectList[i].Sumtime);
        }
    }

    bool flag = 0; // 是否输出latestStartTime
    // 计算最迟开始时间
    for (int i = 1; i <= projectNum; i++)
    {
        projectList[i].latestStartTime = deadline - projectList[i].Sumtime + 1;
        if (projectList[i].latestStartTime <= 0) flag++;
    }

    // 计算最早开始时间
    for (int i = 1; i <= projectNum; i++)
    {
        if (projectList[i].dependProject == 0) // 没有依赖
        {
            projectList[i].earliestStartTime = 1;
        }
        else // 有依赖-依赖项目的最早开始并完成后的日期
        {
            projectList[i].earliestStartTime = projectList[projectList[i].dependProject].earliestStartTime +
                projectList[projectList[i].dependProject].timeSpend;
        }
    }

    for (int i = 1; i <= projectNum; i++)
    {
        cout << projectList[i].earliestStartTime << " ";
    }
    cout << endl;
    if (!flag)
    {
        for (int i = 1; i <= projectNum; i++)
        {
            cout << projectList[i].latestStartTime << " ";
        }
    } 

    return 0;
}