自动搬运

查看原文

来自洛谷，原作者为

	GI录像机 除了OI，除了这个世界，我还是剩点东西的

搬运于2025-08-24 22:48:37，当前版本为作者最后更新于2023-10-30 14:14:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路：

我们考虑从 $0$ 到 $N-1$ 依次把每个总管加入序列，把新总管任意插到序列中的一个合法位置内。

一个总管能够加入序列当且仅当序列中存在一个“空”，使得和这个“空”相邻的总管排名都在前一半。

我们用 $0$ 表示对于 $i$ 排名在前一半的总管，$1$ 表示排名在后一半的总管。

若当前序列中已经有 $len$ 个数。

当 $len$ 为偶数时，最坏情况下序列会变成 $1$ $0$ $1$ $0\cdots 0$，必有至少一个位置可以插入。（因为如果有两个相邻的 $1$ 就可以直接插到中间）

当 $len$ 为奇数时，最坏情况下序列会变成 $1$ $0$ $1$ $0\cdots 1$，必有至少一个位置可以插入。

综上，这种方法必然能构造出一种解。

代码：

#include<bits/stdc++.h>
using namespace std;
int read() {
	int f = 1, x = 0;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-')f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return f * x;
}
void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9)write(x / 10);
	putchar(x % 10 + '0');
}
const int N = 2e5 + 10, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
int n = read();
bool ok[N];
vector<int>ans;
signed main() {
	ans.push_back(0);
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			int tmp = read();
			if (j < i - i / 2)ok[tmp] = 1;
			else ok[tmp] = 0;
		}
		if (ok[ans[i - 1]])ans.push_back(i);
		else {
			for (int j = 0; j < i; j++) {
				bool flag = ok[ans[j]];
				if (j)flag = flag && ok[ans[j - 1]];
				if (flag) {
					ans.insert(ans.begin() + j, i);
					break;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		write(ans[i]);
		putchar(' ');
	}
	return 0;
}