P1065 [NOIP2006 提高组] 作业调度方案
题目描述
我们现在要利用 \(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 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 提高组 第三题
解题思路
模拟，见代码。
C++代码
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
typedef long long LL;
const int N = 30, M = 30;
int n, m, ans;
int order[N * M];
int g[N][N], t[N][N];
int last[N]; // 每个零件上一次加工时间
int step[N]; // 每个零件加工到的工序
int machine[N][N * N * N]; // 机器 i 在第 j 时间是否空闲
int main() {
scanf("%d%d", &m, &n); // 机器数、零件数
for (int i = 1; i <= n * m; i++) // 顺序
scanf("%d", &order[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &g[i][j]); // 零件 i 的第 j 工序所用机器
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &t[i][j]); // 零件 i 的第 j 工序耗时
for (int i = 1; i <= n * m; i++) {
int now = order[i];
step[now]++;
int id = g[now][step[now]], cost = t[now][step[now]];
int s = 0;
for (int j = last[now] + 1; ; j++) {
if (machine[id][j] == 0) {
s++;
} else {
s = 0;
}
if (s == cost) {
for (int k = j - cost + 1; k <= j; k++) {
machine[id][k] = 1;
}
if (j > ans)
ans = j;
last[now] = j;
break;
}
}
}
cout << ans;
return 0;
}
P1067 [NOIP2009 普及组] 多项式输出
题目描述
一元 \(n\) 次多项式可用如下的表达式表示：
\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,a_n\ne 0 \]其中，\(a_ix^i\) 称为 \(i\) 次项，\(a_i\) 称为 \(i\) 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：
-
多项式中自变量为 \(x\)，从左到右按照次数递减顺序给出多项式。
-
多项式中只包含系数不为 \(0\) 的项。
-
如果多项式 \(n\) 次项系数为正，则多项式开头不出
+号，如果多项式 \(n\) 次项系数为负，则多项式以-号开头。 -
对于不是最高次的项，以
+号或者-号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于 \(0\) 次的项，其系数的绝对值为 \(1\)，则无需输出 \(1\)）。如果 \(x\) 的指数大于 \(1\)，则接下来紧跟的指数部分的形式为“\(x^b\)”，其中 \(b\) 为 \(x\) 的指数；如果 \(x\) 的指数为 \(1\)，则接下来紧跟的指数部分形式为 \(x\)；如果 \(x\) 的指数为 \(0\)，则仅需输出系数即可。 -
多项式中，多项式的开头、结尾不含多余的空格。
输入格式
输入共有 \(2\) 行
第一行 \(1\) 个整数，\(n\)，表示一元多项式的次数。
第二行有 \(n+1\) 个整数，其中第 \(i\) 个整数表示第 \(n-i+1\) 次项的系数，每两个整数之间用空格隔开。
输出格式
输出共 \(1\) 行，按题目所述格式输出多项式。
样例 #1
输入样例 #1
5
100 -1 1 -3 0 10
输出样例 #1
100x^5-x^4+x^3-3x^2+10
样例 #2
输入样例 #2
3
-50 0 0 1
输出样例 #2
-50x^3+1
提示
NOIP 2009 普及组 第一题
对于 \(100\%\) 数据，\(0 \le n \le 100\)，$-100 \le $ 系数 $ \le 100$
\(\text{upd 2022.8.1}\)：新增加一组 \(Hack\) 数据。
解题思路
按照指数递减的顺序依次求出每个项的字符串，最后进行拼接。如果系数是负数，则直接拼接；如果系数为正数，则看当前答案的长度是否为零，大于零则说明前面存在项，则需要拼接 +。在求解每一项时需要注意系数为 1 和 -1 的情况、指数为 1 和 0 的情况。
注意：如果最后答案字符串长度为零，则说明所有系数为零，则需要拼接一个 0 作为最后的答案。
C++代码
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
typedef long long LL;
const int N = 110, M = 30;
int n;
int a[N];
string item[N];
int main() {
cin >> n;
for (int i = 0; i <= n; i++)
cin >> a[i];
for (int i = 0; i <= n; i++) {
if (a[i] == 0) {
item[i] = "";
} else {
if (n - i == 0) {
item[i] = "" + to_string(a[i]);
} else if (n - i == 1) {
if (abs(a[i]) != 1) {
item[i] = "" + to_string(a[i]) + "x";
} else {
if (a[i] == -1) {
item[i] = "-x";
} else {
item[i] = "x";
}
}
} else {
if (abs(a[i]) != 1) {
item[i] = "" + to_string(a[i]) + "x^" + to_string(n - i);
} else {
if (a[i] == -1) {
item[i] = "-x^" + to_string(n - i);
} else {
item[i] = "x^" + to_string(n - i);
}
}
}
}
}
string res = "";
for (int i = 0; i <= n; i++) {
if (res.size() == 0) {
res = res + item[i];
} else {
if (item[i].size() > 0 && item[i][0] != '-') {
res = res + "+" + item[i];
} else {
res = res + item[i];
}
}
}
if (res.size() == 0)
res = "0";
cout << res << endl;
return 0;
}