自动搬运

查看原文

来自洛谷，原作者为

	RiverHamster hope invaluable | 曾经是个OIer

搬运于2025-08-24 21:51:34，当前版本为作者最后更新于2018-08-26 21:31:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这题主要要把套娃的拆开合并的方式模拟清楚，手动模拟一下会简单很多。

首先我们考虑一种最简单的完成任务的方法：把套娃全部拆开，然后再合并成所要求的样子，那么原来有父亲的都要拆开一次，把最后要求有父亲的都合并一次。

显然这样不是最优解，原来和现在状态都一样的，我们就不必拆开。一个例子：$5$个套娃连成这样的形状（套娃的关系用链表示）：（$1$最小，$5$最大）

假设我们要拆出$3$，其他的不变，得到如下的形状：

那么$1-2$显然不用拆开，但$4-5$需要拆开来再装上，才能拿出$3$，那么我们的步骤就是：拆掉$5$，拆掉$4$，拆掉$3$，拼上$4$，拼上$5$，共$5$步

我们发现，在一条链中，我们只能保留最小的一部分，其他只要有所更改，套娃更大的部分就不能保留（要拆开才能能取到里面）。因此找出每条链最小的部分就是不用拆开的部分（如这个例子中的$1-2$），两个套娃不用拆开，就可以把原来做法的答案减$2$（拆开一次，拼上一次），就可以最优化答案了。实际操作时，找到在原始状态和目标状态中都是最小的套娃开始向大的去找，直到发现不同就可以了

时间复杂度$O(n)$

code:

#include <cstdio>

int a[100005], b[100005];
bool ntail[100005]; //表示i不是链的结尾

int main(){
    int n, ans = 0;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
		scanf("%d", &a[i]);
		ntail[a[i]] = true; //已经不是链的结尾（最小的套娃）了
		if(a[i] != 0) ans++; //原始做法
	}
    for(int i=1; i<=n; i++){ //同上
    	scanf("%d", &b[i]);
    	ntail[b[i]] = true;
    	if(b[i] != 0) ans++;
	}
	int p;
	for(int i=1; i<=n; i++){
		if(!ntail[i]){ //是链尾
			p = i;
			while(a[p] == b[p] && a[p] != 0 && b[p] != 0){ //一直找相同（可以不拆开的）
				ans -= 2; //避免2次操作
				p = a[p];
			}
		}
	}
    printf("%d\n", ans);
    return 0;
} 

思路来自: 官方题解 BlackJack_的博客