B3746 [语言月赛202304] 洛谷评测机模拟器 题解
Maxmilite
·
·
题解
Source & Knowledge
2023 年 4 月语言月赛，由洛谷网校入门计划/基础计划提供。
题目大意
对于这些评测任务，需要依次找到目前累积评测时间最小的评测节点将任务放入。如果有多个评测节点累积评测时间相同且最小，则找一个标号最小的节点将任务放入。
询问最后这些节点各自处理了哪些任务。
## 题目分析
题目中提到了一个「找到最小」的问题。入门阶段处理这种问题通常会使用擂台法。
具体的，我们使用一个数组 $f$ 记录各个节点的累积评测时间，从头到尾枚举各个任务，对于每个任务，使用擂台法找到 $f$ 中的最小值所对应的标号中最小的一个。
在找到目标标号后，我们需要记录这个信息。一种比较简单的记录方法是，建立一个数组 $g$，其中 $g _ i$ 代表第 $i$ 个评测任务被置入的节点编号，在找到目标标号（设其为 $x$）后，我们直接将 $g _ i$ 赋值为 $x$ 即可。
最终输出答案时，对于每个节点 $x$，我们从头到尾遍历一次 $g$ 数组。当找到了一个 $i$ 使得 $g _ i = x$ 时，我们输出 $i$ 即可。特别的，我们可以用一个记号来记录当前节点是否被输出过。如果没有输出，则需要输出一个 $0$。
特别的，由于一个节点可能承担多个评测任务，一个评测任务至多可以耗费 $10 ^ 9$ 的时间。当一个节点承担超过三个任务时，如果 $f$ 使用 `int` 类型建立，则会产生溢出。因此 $f$ 应当采用 `long long` 类型。
擂台法核心代码：
```cpp
for (int i = 1; i <= m; ++i) {
int pos = 0;
long long cur = 5000000000000;
for (int j = 1; j <= n; ++j) {
if (f[j] < cur) {
cur = f[j];
pos = j;
}
}
g[i] = pos;
f[pos] += t[i];
}
```
输出核心代码：
```cpp
for (int i = 1; i <= n; ++i) {
int flag = 0;
for (int j = 1; j <= m; ++j) {
if (g[j] == i) {
printf("%d ", j);
flag = 1;
}
}
if (flag == 0) {
printf("0");
}
printf("\n");
}
```
## 视频讲解
**完整代码请在视频题解中查看**。
