做网站运营经理的要求,福州短视频seo网红,天津市区县档案部门网站建设指导意见,如何安装wordpress[NOIP2006 提高组] 作业调度方案
题目描述
我们现在要利用 m m m 台机器加工 n n n 个工件#xff0c;每个工件都有 m m m 道工序#xff0c;每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。
每个工件的每个工序称为一个操作#xff0c;…[NOIP2006 提高组] 作业调度方案
题目描述
我们现在要利用 m m m 台机器加工 n n n 个工件每个工件都有 m m m 道工序每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。
每个工件的每个工序称为一个操作我们用记号 j-k 表示一个操作其中 j j j 为 1 1 1 到 n n n 中的某个数字为工件号 k k k 为 1 1 1 到 m m m 中的某个数字为工序号例如 2-4 表示第 2 2 2 个工件第 4 4 4 道工序的这个操作。在本题中我们还给定对于各操作的一个安排顺序。
例如当 n 3 , m 2 n3,m2 n3,m2 时1-1,1-2,2-1,3-1,3-2,2-2 就是一个给定的安排顺序即先安排第 1 1 1 个工件的第 1 1 1 个工序再安排第 1 1 1 个工件的第 2 2 2 个工序然后再安排第 2 2 2 个工件的第 1 1 1 个工序等等。
一方面每个操作的安排都要满足以下的两个约束条件。 对同一个工件每道工序必须在它前面的工序完成后才能开始 同一时刻每一台机器至多只能加工一个工件。
另一方面在安排后面的操作时不能改动前面已安排的操作的工作状态。
由于同一工件都是按工序的顺序安排的因此只按原顺序给出工件号仍可得到同样的安排顺序于是在输入数据中我们将这个安排顺序简写为 1 1 2 3 3 2。
还要注意“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时有可能排在后面的某个操作比前面的某个操作先完成。
例如取 n 3 , m 2 n3,m2 n3,m2已知数据如下机器号/加工时间
工件号工序 1 1 1工序 2 2 2 1 1 1 1 / 3 1/3 1/3 2 / 2 2/2 2/2 2 2 2 1 / 2 1/2 1/2 2 / 5 2/5 2/5 3 3 3 2 / 2 2/2 2/2 1 / 4 1/4 1/4
则对于安排顺序 1 1 2 3 3 2下图中的两个实施方案都是正确的。但所需要的总时间分别是 10 10 10 与 12 12 12。 当一个操作插入到某台机器的某个空档时机器上最后的尚未安排操作的部分也可以看作一个空档可以靠前插入也可以靠后或居中插入。为了使问题简单一些我们约定在保证约束条件 1 1 1 2 2 2的条件下尽量靠前插入。并且我们还约定如果有多个空档可以插入就在保证约束条件 1 1 1 2 2 2的条件下插入到最前面的一个空档。于是在这些约定下上例中的方案一是正确的而方案二是不正确的。
显然在这些约定下对于给定的安排顺序符合该安排顺序的实施方案是唯一的请你计算出该方案完成全部任务所需的总时间。
输入格式
第 1 1 1 行为两个正整数 m m m, n n n用一个空格隔开 其中 m ( 20 ) m(20) m(20) 表示机器数 n ( 20 ) n(20) n(20) 表示工件数
第 2 2 2 行 m × n m \times n m×n 个用空格隔开的数为给定的安排顺序。
接下来的 2 n 2n 2n 行每行都是用空格隔开的 m m m 个正整数每个数不超过 20 20 20。
其中前 n n n 行依次表示每个工件的每个工序所使用的机器号第 1 1 1 个数为第 1 1 1 个工序的机器号第 2 2 2 个数为第 2 2 2 个工序机器号等等。
后 n n n 行依次表示每个工件的每个工序的加工时间。
可以保证以上各数据都是正确的不必检验。
输出格式 1 1 1 个正整数为最少的加工时间。
样例 #1
样例输入 #1
2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4样例输出 #1
10提示
NOIP 2006 提高组 第三题
解题思路
当处理这个问题时我们可以将其类比成一个工厂里的任务分配问题。下面是一个小学生都能理解的解题思路附带一些简单的代码解释。
1.明确问题 我们有很多台机器和很多个任务每个任务都有几个步骤每个步骤都需要在某个机器上完成并且需要花一些时间。
2.获取机器和任务数量 首先从输入中读取机器和任务的数量。
int numMachines, numJobs;
cin numMachines numJobs;3.记录每个任务的信息 对于每个任务我们需要知道每个步骤应该在哪台机器上完成以及需要花多少时间。
struct JobStep {int machineId;int timeCost;
};JobStep jobs[21][21]; // 假设最多有 20 个任务每个任务最多 20 个步骤
4.获取任务步骤的信息 针对每个任务和每个步骤读取它应该在哪台机器上完成以及需要花多少时间。
for (int i 1; i numJobs; i) {for (int j 1; j numMachines; j) {cin jobs[i][j].machineId;}
}for (int i 1; i numJobs; i) {for (int j 1; j numMachines; j) {cin jobs[i][j].timeCost;}
}
5.任务列表 我们会获取一个任务列表告诉我们任务的执行顺序。
int jobList[501]; // 假设最多有 500 个任务步骤for (int i 1; i numMachines * numJobs; i) {cin jobList[i];
}
6.模拟执行 对于每个任务步骤我们会找到合适的时间段然后更新机器的时间线并记录任务的完成时间。这段代码比较难以理解所以我把他再次分为几点
int machineTimeline[21][100001] {0}; // 机器时间线用 0 表示空闲1 表示占用
int jobStep[21] {0}; // 每个任务完成的步骤
int lastJobTime[21] {0}; // 每个任务的上次完成时间
int answer 0; // 最终答案所有任务都完成的时间点6.1这些数组用于存储我们模拟中需要的信息。machineTimeline 记录每台机器的时间线jobStep 记录每个任务已经完成的步骤数lastJobTime 记录每个任务上一次完成的时间answer 存储最终的答案即所有任务都完成的时间点。
for (int i 1; i numMachines * numJobs; i) {int currentJob jobList[i];jobStep[currentJob];int currentMachineId jobs[currentJob][jobStep[currentJob]].machineId;int currentTimeCost jobs[currentJob][jobStep[currentJob]].timeCost;int s 0;for (int j lastJobTime[currentJob] 1; ; j) {if (machineTimeline[currentMachineId][j] 0) {s;} else {s 0;}if (s currentTimeCost) {for (int k j - currentTimeCost 1; k j; k) {machineTimeline[currentMachineId][k] 1;}if (j answer) answer j;lastJobTime[currentJob] j;break;}}
}
我们通过循环来模拟处理每个任务步骤。currentJob 是当前任务步骤对应的任务编号。我们递增jobStep[currentJob]表示当前任务已完成的步骤数。然后我们获取当前步骤需要在哪台机器上执行以及需要多少时间。我们使用 s来记录在机器上找到的可用时间段的长度。我们从上次这个任务完成的时间lastJobTime[currentJob]的下一个时间点开始查找。我们检查 machineTimeline[currentMachineId][j]如果等于 0表示这个时间点机器是空闲的我们递增 s否则表示机器正在被占用我们将 s 重置为 0。当 s 的值达到当前步骤所需的时间时说明我们找到了一个满足条件的时间段。我们将从 j - currentTimeCost 1 到j 的时间段标记为机器被占用。如果当前时间点 j 大于记录的 answer我们更新 answer以便在之后输出。最后我们更新 lastJobTime[currentJob]表示当前任务上一次完成的时间。
注意s的解释 在这段代码中s 是用来计算连续空闲时间段的计数器。当我们需要找到一个连续时间段足够容纳当前步骤所需的时间时我们使用 s 来记录连续空闲时间段的长度。
在循环中我们逐步递增 j检查机器时间线上的每个时间点。如machineTimeline[currentMachineId][j] 表示机器上的这个时间点空闲值为 0那么我们递增 s。如果不是空闲的我们将 s 重置为 0因为我们需要找到连续的空闲时间段。
当 s 的值等于当前步骤所需的时间时s currentTimeCost说明我们找到了一个足够长的连续空闲时间段可以在机器上执行当前任务步骤。然后我们会将这个时间段标记为机器被占用并更新相应的时间和计数器。
所以s 在这里充当了一个计数器帮助我们在机器时间线上找到足够长的连续空闲时间段以满足当前任务步骤的时间要求。
最后附上完整代码
#include iostreamusing namespace std;int numMachines, numJobs;
int jobList[501];
struct JobInfo {int machineId;int timeCost;
} jobs[21][21];
int machineTimeline[21][100001] {0};
int jobStep[21] {0};
int lastJobTime[21] {0};
int answer 0;int main() {// 读取机器和任务数量cin numMachines numJobs;// 读取任务列表for (int i 1; i numMachines * numJobs; i) {cin jobList[i];}// 读取每个任务步骤的机器编号for (int i 1; i numJobs; i) {for (int j 1; j numMachines; j) {cin jobs[i][j].machineId;}}// 读取每个任务步骤的时间花费for (int i 1; i numJobs; i) {for (int j 1; j numMachines; j) {cin jobs[i][j].timeCost;}}// 处理每个任务for (int i 1; i numMachines * numJobs; i) {int currentJob jobList[i];jobStep[currentJob];int currentMachineId jobs[currentJob][jobStep[currentJob]].machineId;int currentTimeCost jobs[currentJob][jobStep[currentJob]].timeCost;int s 0;// 查找机器上的下一个可用时间段for (int j lastJobTime[currentJob] 1; ; j) {if (machineTimeline[currentMachineId][j] 0) {s;} else {s 0;}if (s currentTimeCost) {// 更新机器时间线以表示当前任务for (int k j - currentTimeCost 1; k j; k) {machineTimeline[currentMachineId][k] 1;}// 使用最新的完成时间更新答案if (j answer) answer j;// 更新当前任务的上次完成时间lastJobTime[currentJob] j;break;}}}// 输出最终答案cout answer;return 0;
}
