自动搬运

查看原文

来自洛谷，原作者为

	sxyugao **

搬运于2025-08-24 21:44:09，当前版本为作者最后更新于2018-06-27 10:27:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

总的证明楼下的yyhhenry大佬已经写了，如果想了解更多细节或者看不懂他证明的可以去我博客上看。

我主要是证明他的那个引理：

对于两个长度为n的01串，A中a个1，B中b个1，任一排列中相同位置元素相同的数量至少为max(a+b-n,n-a-b)，通过分别分析0和1就可以得到。

我们仍然使用引理中的变量，进行分类讨论：

1、$a+b>n$，即 $A$ 和 $B$ 匹配1。

我们为了让相同元素尽可能少，考虑把 $A$ 中的1全移到前端，$B$ 中的1全移到后端，变成线段覆盖问题，重合部分为 $a+b-n$。

2、$a+b<n$，即 $A$ 和 $B$ 匹配0.

同理，我们考虑把 $A$ 中的0全移到前端，$B$ 中的0全移到后端，用同样的方法得出该情况下结果为 $n-a-b$。

3、$a+b=n$，显然答案为0。

主要证明和代码请移步：https://sxyugao.top/p/1192747.html#solution