天水市网站建设,wordpress them8主题,成都装修公司一览表,如何自己建设电影网站CSP-202212-2-训练计划
解题思路 输入和初始化#xff1a; 首先#xff0c;代码从输入中获取项目的截止日期和项目数量。然后#xff0c;它初始化一个项目列表#xff0c;每个项目都有其依赖项、被依赖的项目集合、完成时间、总完成时间#xff08;包括依赖链#xff09…CSP-202212-2-训练计划
解题思路 输入和初始化 首先代码从输入中获取项目的截止日期和项目数量。然后它初始化一个项目列表每个项目都有其依赖项、被依赖的项目集合、完成时间、总完成时间包括依赖链、最早和最晚开始时间。 建立依赖关系 通过输入确定每个项目的依赖项目。如果一个项目依赖另一个项目那么被依赖的项目的集合会更新加入依赖它的项目。同时记录每个项目的直接完成时间。 计算总完成时间Sumtime 从后向前遍历项目列表如果一个项目有依赖即它不是独立的则更新它依赖的项目的总完成时间为当前项目的总完成时间加上依赖项目的直接完成时间的最大值。 计算最迟开始时间 遍历项目列表每个项目的最迟开始时间等于截止日期减去该项目的总完成时间加一。如果计算出的最迟开始时间小于或等于0则标记flag表示存在项目不能在截止日期前完成。 计算最早开始时间 遍历项目列表如果一个项目没有依赖即其依赖项目编号为0其最早开始时间为1。如果项目有依赖其最早开始时间为依赖项目的最早开始时间加上依赖项目的完成时间。 输出 最后代码输出每个项目的最早和最晚开始时间。如果flag被设置意味着有项目无法按时完成则只输出最早开始时间。
完整代码
#include iostream
#include vector
#include cmath
using namespace std;struct MyProject
{int dependProject; // 依赖哪一个项目0是无依赖项目vectorintdependSet; // 被依赖的项目集合int timeSpend; // 完成本任务所需要的时间int Sumtime; // 完成任务依赖链所需时间int earliestStartTime; // 最早开始时间int latestStartTime; //最迟开始时间
};int main() {int deadline, projectNum;cin deadline projectNum;vectorMyProjectprojectList(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;}// 计算每个任务的Sumtimefor (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;
}
