网站建设方案ppt模板,唐山企业建网站,360网站优化,做网站单页烧钱题目
问题背景 西西艾弗岛荒野求生大赛还有 天开幕#xff01;
问题描述 为了在大赛中取得好成绩#xff0c;顿顿准备在 天时间内完成“短跑”、“高中物理”以及“核裂变技术”等总共 项科目的加强训练。其中第 项#xff08; #xff09;科目编号为 #xff0c;也可简…题目
问题背景 西西艾弗岛荒野求生大赛还有 天开幕
问题描述 为了在大赛中取得好成绩顿顿准备在 天时间内完成“短跑”、“高中物理”以及“核裂变技术”等总共 项科目的加强训练。其中第 项 科目编号为 也可简称为科目 。已知科目 耗时 天即如果从第 天开始训练科目 那么第 天就是该项训练的最后一天。
大部分科目的训练可以同时进行即顿顿在同一天内可以同时进行多项科目的训练但部分科目之间也存在着依赖关系。如果科目 依赖科目 那么只能在后者训练结束后科目 才能开始训练。具体来说如果科目 从第 天训练到第 天那么科目 最早只能从第 天开始训练。还好顿顿需要训练的 项科目依赖关系并不复杂每项科目最多只依赖一项别的科目且满足依赖科目的编号小于自己。那些没有任何依赖的科目则可以从第 天就开始训练。
对于每一项科目试计算
1最早开始时间该科目最早可以于哪一天开始训练
2最晚开始时间在不耽误参赛的前提下 天内完成所有训练该科目最晚可以从哪一天开始训练
天内完成所有训练即每一项科目训练的最后一天都要满足 。需要注意顿顿如果不能在 天内完成全部 项科目的训练就无法参加大赛。这种情况下也就不需要再计算“最晚开始时间”了。
输入格式 从标准输入读入数据。
输入共三行。
输入的第一行包含空格分隔的两个正整数 和 分别表示距离大赛开幕的天数和训练科目的数量。
输入的第二行包含空格分隔的 个整数其中第 个 整数 表示科目 依赖的科目编号满足 表示科目 无依赖。
输入的第三行包含空格分隔的 个正整数其中第 个 数 表示训练科目 所需天数满足 。
输出格式 输出到标准输出中。
输出共一行或两行。
输出的第一行包含空格分隔的 个正整数依次表示每项科目的最早开始时间。
如果顿顿可以在 天内完成全部 项科目的训练则继续输出第二行否则输出到此为止。
输出的第二行包含空格分隔的 个正整数依次表示每项科目的最晚开始时间。
代码
AC
#includebits/stdc.h
using namespace std;struct
{int form0;//先导课int day0;//消耗int start1;//最早int last_start0;//最晚
}course[105]; int main()
{int max-1;int n,m;cinnm;for(int i0;im;i){cincourse[i].form;}for(int i0;im;i){cincourse[i].day;}for(int i0;im;i){if(course[i].form ! 0){course[i].start course[course[i].form-1].startcourse[course[i].form-1].day;//该门课的最早开始时间为先导课最早结束时间}coutcourse[i].start ;//输出最早开始时间 if((course[i].daycourse[i].start)max)//判断是否能上完课 maxcourse[i].daycourse[i].start-1; }if(maxn)//能上就输出 {coutendl;for(int im-1;i0;i--){if(course[i].last_start0)course[i].last_startn-course[i].day1;if(course[i].form ! 0){int temp course[i].last_start-course[course[i].form-1].day ;if(course[course[i].form-1].last_start 0){course[course[i].form-1].last_start temp ;}else{course[course[i].form-1].last_start min(temp,course[course[i].form-1].last_start);}}}for(int i0;im;i){coutcourse[i].last_start ;}}return 0;
}/*
14 7
0 1 0 3 2 3 0
2 1 6 3 10 4 3
*//*
51 5
0 1 2 3 4
10 10 10 10 10*/
