自动搬运

查看原文

来自洛谷，原作者为

	I_Love_DS csp 前 at 上 1400

搬运于2025-08-24 23:06:59，当前版本为作者最后更新于2024-12-14 18:41:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

更好的阅读体验？

Subtask #1

分类讨论即可。

时间复杂度 $O(1)$。

Subtask #2

暴力搜索每个猫猫后面要不要放隔板。假设最后一只猫后面一定要放隔板。再进行 $O(n)$ 的判定合法并更新答案。

时间复杂度 $O(n2^n)$。

Code:

struct node {
	int x, y;
	friend bool operator < (const node &x, const node &y) {
		return x.x == y.x ? x.y < y.y : x.x < y.x;
	}
} b[N];

bool check() {
	for (int i = 1; i <= n; i++) {
		if (q[i] < b[i].y) return 1;
		else if (q[i] > b[i].y) return 0;
	}
	return 0;
}

void subtask2() {
	for (int i = 1; i <= n; i++) q[i] = -1;
	for (int i = 1 << (n - 1); i < (1 << n); i++) {
		int l = 0;
		for (int j = 0; j < n; j++) 
			if (i & (1 << j)) {
				int mn = 1 << 30;
				for (int k = l + 1; k <= j + 1; k++) 
					mn = min(mn, a[k]);
				for (int k = l + 1; k <= j + 1; k++) 
					b[k] = {mn, a[k]};
				l = j + 1;
			}
		sort(b + 1, b + n + 1);
		if (check()) 
			for (int j = 1; j <= n; j++) 
				q[j] = b[j].y;
	}
	for (int i = 1; i <= n; i++) 
		printf("%d ", q[i]);
}

Subtask #4

显然 $a_k$ 最小。那么根据题意，应让字典序最大。

你会发现无论怎么分，$a_k$ 总是在第一位。

那么定下了第一位为 $a_k$，剩下的呢？

应当以 $a_k$ 为连通块的区域进行分第一组。因为由题可知一组组内成员一定在其他组的前面。

那么我们要使第二位尽可能大，应当选择 $a_k$ 左面或右面更大者。可以证明只选左/右面优于左右都选。因为都选的话第二个值就会变成左右最小值了。

因为 $a$ 是 $1 \sim n$ 的一个排列，所以不用担心 $a_{k-1}=a_{k+1}$ 的问题。

选完了第一组，剩下的就全是第二组啦！

也许我的语言并不完善，边看代码边食用更佳。

void subtask4() {
	int k = 0;
	for (int i = 1; i <= n && !k; i++) 
		if (a[i] == 1) 
			k = i; // 找到最小值 a[k]
	if (a[k - 1] > a[k + 1]) { // 找更大的当答案的第二位
		for (int i = k; i; --i) 
			printf("%d ", a[i]); // 根据性质
		for (int i = k + 1; i <= n; i++) 
			printf("%d ", a[i]); // 
	} else {
		for (int i = k; i <= n; i++) 
			printf("%d ", a[i]); // 
		for (int i = k - 1; i; --i) 
			printf("%d ", a[i]); // 
	}
	printf("\n");
}

Subtask #5

可以从 Subtask #4 推广而来。

更一般的，假设当前选了若干组，剩下猫猫的集合为 $S$。

那么当前 $S$ 内的最小值（记为 $x$）就是下一个入场的猫猫。

根据 Subtask #4 的结论，我们应选择 $x$ 左面或右面的元素，这取决于哪边的元素更大。

代码实现时，可以用堆或者 set 来维护 $S$。我们还要记录这个猫猫是否已经在队伍里了。详见代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 50;

int n, a[N], q[N];

set <int> s; // 集合 S，本代码使用 set 实现
int id[N], vis[N];
// id 是这个猫猫的下标，vis 是这个猫猫是否进队

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) id[a[i]] = i;
	for (int i = 1; i <= n; i++) s.insert(a[i]); // 最初所有猫猫都在 S 里
	vis[0] = vis[n + 1] = 1; // 方便后续代码，不用再判边界
	while (!s.empty()) { // 有猫猫没进队
		int x = *s.begin(), y = id[x]; // a[y] 为最小猫猫入场时间
		//cerr << x << " " << y << endl; // 114514
		vis[y] = 1; // 取走啦
		s.erase(x); // 删除啦
		printf("%d ", x); // 进队啦
		if (!vis[y - 1] && !vis[y + 1]) { // 都没有取走呀
			if (a[y - 1] > a[y + 1]) { // 左面的更大捏
				vis[y - 1] = 1; // 取走啦
				s.erase(a[y - 1]); // 删除啦
				printf("%d ", a[y - 1]); // 进队啦
				for (int i = y - 2; i >= 1 && a[i] > a[i + 1] && !vis[i]; i--) {
					vis[i] = 1;
					s.erase(a[i]);
					printf("%d ", a[i]);
				} // 自行理解吧
			} else { // 右面的更大捏
				vis[y + 1] = 1; // 取走啦
				s.erase(a[y + 1]); // 删除啦
				printf("%d ", a[y + 1]); // 进队啦
				for (int i = y + 2; i <= n && a[i] > a[i - 1] && !vis[i]; i++) {
					vis[i] = 1;
					s.erase(a[i]);
					printf("%d ", a[i]);
				} // 自行理解吧	
			}
		} else if (!vis[y - 1]) { // 只有左面有猫猫
			vis[y - 1] = 1; // 取走啦
			s.erase(a[y - 1]); // 删除啦
			printf("%d ", a[y - 1]); // 进队啦
			for (int i = y - 2; i >= 1 && a[i] > a[i + 1] && !vis[i]; i--) {
				vis[i] = 1;
				s.erase(a[i]);
				printf("%d ", a[i]);
			} // 自行理解吧	
		} else if (!vis[y + 1]) { // 只有右面有猫猫
			vis[y + 1] = 1; // 取走啦
			s.erase(a[y + 1]); // 删除啦
			printf("%d ", a[y + 1]); // 进队啦
			for (int i = y + 2; i <= n && a[i] > a[i - 1] && !vis[i]; i++) {
				vis[i] = 1;
				s.erase(a[i]);
				printf("%d ", a[i]);
			} // 自行理解吧	
		}
	}
	return 0;
}

看我写了这么多，留下个赞不过分吧……