自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:47，当前版本为作者最后更新于2023-04-28 00:38:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2023 年 4 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

$n$ 个运算节点需要依次处理 $m$ 个任务。这些任务耗时依次为 $t _ 1, t _ 2, \cdots, t _ m$。

对于这些评测任务，需要依次找到目前累积评测时间最小的评测节点将任务放入。如果有多个评测节点累积评测时间相同且最小，则找一个标号最小的节点将任务放入。

询问最后这些节点各自处理了哪些任务。

题目分析

题目中提到了一个「找到最小」的问题。入门阶段处理这种问题通常会使用擂台法。

具体的，我们使用一个数组 $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 类型。

擂台法核心代码：

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];
}

输出核心代码：

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");
}

视频讲解

完整代码请在视频题解中查看。