自动搬运

查看原文

来自洛谷，原作者为

	vegetable_king 全身全霊！MORE MORE JUMP!!

搬运于2025-08-24 22:34:13，当前版本为作者最后更新于2021-10-24 00:07:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

在博客食用更佳。

思路

容易想到，可以把每一个块看成一个整体。

由于队列先进先出的特性，可以使用队列维护块。

需要注意的是，当两个块在队列里相邻且元素相同，就可以直接合并。

然后这道题就变成了一道模拟啦！

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

struct kuai{ // 块
	int st, ed, th;
}f, x, ad;
int n, cnt, t[200002];
queue<kuai> q, q2;
bool used[200001]; // 记录是否被取出
int main(){
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d", &t[i]);
	t[n + 1] = !t[n];
	for (int i = 2, si = 1;i <= n + 1;i ++){
		if (t[i] != t[i - 1]) q.push((kuai){si, i - 1, t[i - 1]}), si = i; // 把连续一段相同的元素合成一个块
	}
	cnt = n;
	while (cnt){
		while (q.size()){
			f = q.front();
			q.pop();
			while (used[f.st] && f.st <= f.ed) f.st ++; // 如果已经被取了
			if (f.st > f.ed) continue;
			printf("%d ", f.st), cnt --;
			used[f.st] = 1; // 将块的开头元素去掉并输出
			if (f.ed == f.st) continue; // 如果这个块被取完了
			f.st ++;
			q2.push(f); // 先临时存到 q2 里进行合并
		}
		putchar('\n');
		while (q2.size()){
			ad = q2.front();
			q2.pop();
			while (q2.size()){
				x = q2.front();
				if (x.th == ad.th){ // 能合并就合并
					ad.ed = x.ed;
					q2.pop();
				}
				else break;
			}
			q.push(ad); // 丢回 q 里
		}
	}
}

关于时间复杂度

原本，在这种做法里，每一个水果只会被删除一次，最多会删除 $n$ 次。但是，我的代码实现的可能不太好，最坏时间复杂度是 $O(n \sqrt n)$ 的，为了保留每个元素原本的位置，我使用了一个 bool 数组，对每块里的数进行类似于懒惰删除法的操作（见代码中“如果已经被取了”一行），构造 00000000111111000011011000011111100000000 这样的数据可以将这部分卡到移动 $O(n \sqrt n)$ 次。像这样的做法实现应该是可以做到 $O(n)$ 的，如果做到了，欢迎与作者讨论实现方式。