作为一道英文题,我们先解释一下题意:
给你一个长度为 $n$ 的 01 串,其中可能至少有 $t_{i}$ 个 1,问最后你给出一个 01 串可能和其匹配的最大长度。
接下来我们进入正题。
第一眼看见觉得是水题,对于每个 $t_{i}$ 枚举应该全 0 还是全 1,但是这显然可以找出反例来。
那么我们应该怎么贪心呢?
首先,我们先提出一个引理:
对于两个长度为 $n$ 的 01 串,$A$ 中 $a$ 个 1,$B$ 中 $b$ 个 1,任一排列中相同位置元素相同的数量至少为 $\max\{a+b-n,n-a-b\}$。
接下来我们证明一下。
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。
说完了引理,我们再接着讲题。
我们先将 $t$ 从小到大排序,设当前要匹配的 01 串为 $S$,其中有 $x$ 个 1。
对于每对 $t_{i-1},t_{i}$,我们肯定是拿 $S$ 和 $t_{i-1}$ 去匹配 0,和 $t_{i}$ 去匹配 1。
由引理得 $Ans=\max\{n-t_{i-1}-x,t_{i}+x-n\}$。
当 $n-t_{i-1}-x \geq t_{i}+x-n$ 时,
得 $Ans \geq (t_{i}-t_{i-1})/2$
同理当 $n-t_{i-1}-x \geq t_{i}+x-n$ 时,
得 $Ans \geq (t_{i}-t_{i-1})/2$
综上所述,必有 $Ans \geq (t_{i}-t_{i-1})/2$。
然后特判一下 $t_{1}$ 和 $t_{m}$,全选 0 或全选 1 的情况。
于是我们就可以愉快地切题了。
以下为代码:
1 |
|