曾彪彪的个人网站
首页
文章列表
>>
文章详情
模拟题的天花板,花3天才搞明白
作者:
曾彪彪
日期:
2025-07-21 05:57:24
阅读(47)
分类:
问题记录
Algorithm
# P1065 [NOIP 2006 提高组] 作业调度方案 ## 题目描述 我们现在要利用 $m$ 台机器加工 $n$ 个工件,每个工件都有 $m$ 道工序,每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。 每个工件的每个工序称为一个操作,我们用记号 `j-k` 表示一个操作,其中 $j$ 为 $1$ 到 $n$ 中的某个数字,为工件号;$k$ 为 $1$ 到 $m$ 中的某个数字,为工序号,例如 `2-4` 表示第 $2$ 个工件第 $4$ 道工序的这个操作。在本题中,我们还给定对于各操作的一个安排顺序。 例如,当 $n=3,m=2$ 时,`1-1,1-2,2-1,3-1,3-2,2-2` 就是一个给定的安排顺序,即先安排第 $1$ 个工件的第 $1$ 个工序,再安排第 $1$ 个工件的第 $2$ 个工序,然后再安排第 $2$ 个工件的第 $1$ 个工序,等等。 一方面,每个操作的安排都要满足以下的两个约束条件。 1. 对同一个工件,每道工序必须在它前面的工序完成后才能开始; 2. 同一时刻每一台机器至多只能加工一个工件。 另一方面,在安排后面的操作时,不能改动前面已安排的操作的工作状态。 由于同一工件都是按工序的顺序安排的,因此,只按原顺序给出工件号,仍可得到同样的安排顺序,于是,在输入数据中,我们将这个安排顺序简写为 `1 1 2 3 3 2`。 还要注意,“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时,有可能排在后面的某个操作比前面的某个操作先完成。 例如,取 $n=3,m=2$,已知数据如下(机器号/加工时间): 工件号 |工序 1 | 工序 2 -|-|- $1$ | $1/3$ | $2/2$ $2$ | $1/2$ | $2/5$ $3$ | $2/2$ | $1/4$ 则对于安排顺序 `1 1 2 3 3 2`,下图中的两个实施方案都是正确的。但所需要的总时间分别是 $10$ 与 $12$。 方案 1,用时 $10$: | 时间 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :-------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 机器 1 执行工序 | `1-1` | `1-1` | `1-1` | `2-1` | `2-1` | `3-2` | `3-2` | `3-2` | `3-2` | 无 | | 机器 2 执行工序 | `3-1` | `3-1` | 无 | `1-2` | `1-2` | `2-2` | `2-2` | `2-2` | `2-2` | `2-2` | 方案 2,用时 $12$: | 时间 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | :-------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 机器 1 执行工序 | `1-1` | `1-1` | `1-1` | `2-1` | `2-1` | 无 | 无 | `3-2` | `3-2` | `3-2` | `3-2` | 无 | | 机器 2 执行工序 | 无 | 无 | 无 | `1-2` | `1-2` | `3-1` | `3-1` | `2-2` | `2-2` | `2-2` | `2-2` | `2-2` | 当一个操作插入到某台机器的某个空档时(机器上最后的尚未安排操作的部分也可以看作一个空档),可以靠前插入,也可以靠后或居中插入。为了使问题简单一些,我们约定:在保证约束条件 $(1.)(2.)$ 的条件下,尽量靠前插入。并且,我们还约定,如果有多个空档可以插入,就在保证约束条件 $(1.)(2.)$ 的条件下,插入到最前面的一个空档。于是,在这些约定下,上例中的方案一是正确的,而方案二是不正确的。 显然,在这些约定下,对于给定的安排顺序,符合该安排顺序的实施方案是唯一的,请你计算出该方案完成全部任务所需的总时间。 ## 输入格式 第 $1$ 行为两个正整数 $m$, $n$,用一个空格隔开, 其中 $m(<20)$ 表示机器数,$n(<20)$ 表示工件数。 第 $2$ 行:$m \times n$ 个用空格隔开的数,为给定的安排顺序。 接下来的 $2n$ 行,每行都是用空格隔开的 $m$ 个正整数,每个数不超过 $20$。 其中前 $n$ 行依次表示每个工件的每个工序所使用的机器号,第 $1$ 个数为第 $1$ 个工序的机器号,第 $2$ 个数为第 $2$ 个工序机器号,等等。 后 $n$ 行依次表示每个工件的每个工序的加工时间。 可以保证,以上各数据都是正确的,不必检验。 ## 输出格式 $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 提高组 第三题 这道题我每天花一点时间来抠,3天才写出来,理解题意花了2天,写代码模拟花了1天,结果还是未能通过,只得了20分。第一次提交的代码如下: ```c++ /** start time: 14:17 End time: Spend Time: 3 days Type: simulator Solution: - define a two decimion array to store product handling steps, machine ID and time. vector<int,vector<int, pair<int, int>> matrix - define an array to record the machine waiting time, if it's 0, the machine can be used. - define a timer, check if the product handling status, if it is complete, move to next step - if all product finished, break. - test case: - 2 3 1 1 2 3 3 2 1 2 1 2 2 1 3 2 2 5 2 4 - - 3 4 1 1 1 2 2 3 3 4 2 3 4 4 1 2 3 1 2 3 3 1 1 2 2 3 2 3 5 3 3 1 6 1 1 5 1 3 - 3 3 1 1 1 2 3 3 2 2 3 1 2 3 2 1 3 2 3 1 7 2 4 3 2 5 3 2 3 - 3 3 1 1 1 2 2 2 3 3 3 1 1 1 1 2 1 1 1 1 5 5 5 5 5 5 5 5 5 - first submit score: 100 cause: **/ #include <bits/stdc++.h> using namespace std; struct Product { int id; vector<pair<int, int>> steps; int currentStep = 0; bool complete() { return currentStep >= steps.size(); } Product(int id) : id(id) {} Product() {} }; vector<Product> products; vector<int> machines(20, 0); int m, n; void init() { cin >> m >> n; vector<int> seq(m * n); for (int i = 0; i < seq.size(); i++) { cin >> seq[i]; } for (int i = 0; i < n; i++) { Product p(i + 1); for (int j = 0; j < m; j++) { int ma; cin >> ma; pair<int, int> step = {ma, 0}; p.steps.push_back(step); } products.push_back(p); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> products[i].steps[j].second; } } } void start() { int t = 0; while (true) { t++; // cout << "-------" << t << "--------" << endl; for (auto &p : products) { if (p.complete()) { continue; } pair<int, int> &step = p.steps[p.currentStep]; if (machines[step.first] == 0) { machines[step.first] = p.id; // cout << p.id << "-" << p.currentStep << " entered " << step.first << endl; } if (machines[step.first] == p.id) { step.second--; // cout << p.id << "-" << p.currentStep << ":" << step.second << endl; continue; } // cout << endl; } int finishedCount = 0; for (auto &p : products) { if (p.steps[p.currentStep].second == 0) { machines[p.steps[p.currentStep].first] = 0; p.currentStep++; } if (p.complete()) { finishedCount++; } } if (finishedCount >= n) { break; } } cout << t; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin); init(); start(); return 0; } ``` 我下载错误的测试数据点,发现我的运算结果与标准答案一致,所以初步判断应该是超时了. `` 19 19 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ``` 刚开始以为数据都只有20,应该不会超时,后来还是超时了,需要优化。 看了其它人的题解,可以不用使用while循环,类似于定时器的方法。直接在机器时间线上标记,哪个时间片用完了就打上标记,之后的操作,只能在未被标记的时间片上分配时间。 另外就是我的审题有错误,我没有用到工序列表,如: ```c++ cin >> seq[i]; // 输入之后,再也没用到seq ``` 重新整理后的代码如下: ```c++ /** start time: 14:17 End time: Spend Time: 3 days Type: simulator Solution: - define a two decimion array to store product handling steps, machine ID and time. vector<int,vector<int, pair<int, int>> matrix - define an array to record the machine waiting time, if it's 0, the machine can be used. - define a timer, check if the product handling status, if it is complete, move to next step - if all product finished, break. - test case: - 2 3 1 1 2 3 3 2 1 2 1 2 2 1 3 2 2 5 2 4 - - 3 4 1 1 1 2 2 3 3 4 2 3 4 4 1 2 3 1 2 3 3 1 1 2 2 3 2 3 5 3 3 1 6 1 1 5 1 3 - 3 3 1 1 1 2 3 3 2 2 3 1 2 3 2 1 3 2 3 1 7 2 4 3 2 5 3 2 3 - 3 3 1 1 1 2 2 2 3 3 3 1 1 1 1 2 1 1 1 1 5 5 5 5 5 5 5 5 5 - - 3 8 6 4 5 1 7 8 4 2 6 5 2 4 1 2 6 8 3 7 1 3 3 7 5 8 1 2 3 1 3 2 3 2 1 2 1 3 3 1 2 1 2 3 3 1 2 1 2 3 4 5 2 3 5 3 6 4 2 4 5 6 3 1 7 7 5 3 4 4 5 8 5 9 first submit score: 100 cause: **/ #include <bits/stdc++.h> using namespace std; int m, n, maxn = 20; vector<int> stepSeq(maxn *maxn, 0); vector<vector<pair<int, int>>> stepInfo(maxn, vector<pair<int, int>>(maxn, {0, 0})); vector<vector<int>> timeline(maxn, vector<int>(maxn *maxn *maxn, 0)); vector<int> steps(maxn, 0); vector<int> lastTime(maxn, 0); void init() { cin >> m >> n; for (int i = 1; i <= m * n; i++) { cin >> stepSeq[i]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> stepInfo[i][j].first; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> stepInfo[i][j].second; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin); init(); int ans = 0; for (int i = 1; i <= m * n; i++) { int projectId = stepSeq[i]; steps[projectId]++; int projectStep = steps[projectId]; pair<int, int> info = stepInfo[projectId][projectStep]; int machineId = info.first; int stepCost = info.second; int count = 0; for (int j = lastTime[projectId] + 1;; j++) { if (timeline[machineId][j] == 0) { count++; } else { count = 0; // count==0; // a bug here } if (count == stepCost) { for (int k = j; k > j - stepCost; k--) { timeline[machineId][k] = projectId; } lastTime[projectId] = j; ans = max(ans, j); break; } } } for (int i = 1; i <= m; i++) { // for debug test // prit all projectId and verify the data for (int j = 1; j <= 50; j++) { cout << timeline[i][j]; } cout << endl; } cout << ans; return 0; } ``` 第一次提交代码时,有一个bug,只得了37分,把count=0写成了count==0,因为数据量大,这个问题不太好调试,所以增加了输出,方便验证。 修复bug后,问题解决。
评论(0)
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)
提交
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)