均分 01

给定一个 01 串，恰好包含 2n 个 0 和 2n 个 1，你可以把它切成若干段，再把它们任意拼接，要求拼接除两部分，每部分恰好包含 n 个 0，n 个 1，如何使得切的段数最少？

例1：0101，从中间切变成01 01，分别作为两部分

例2：0011，切成三段 0 01 1，中间的 01 作为一部分，剩余的 0 1 拼接起来作为第二部分

分析

下标从 0 开始，f(x) (x=0,1,...,2n) 表示原串在 [x....x+2n-1] 的一段中 0 的个数与 1 的个数的差。

那么 f(0) + f(2n) = 0 （恰好是全部的 0 和 1）

• 如果 f(0) = f(2n) = 0 相当于从中间切一刀成两段，可以完成，答案是 2
• 否则 f(0) < 0 (或者 >0) f(2n) > 0 (或者 <0)
  • f(x) 始终是偶数
  • 窗口滑动 f(x) -> f(x+1)
    • 0 和 1 的个数不变 差不变
    • 多了个 0，少了个 1，增加 2
    • 少了个 0，多了个 1，减少 2

窗口滑动过程中，偶数由负数到正数(或者由正数到负数)的过程中，必然能出现 f(y) = 0，即存在 0<=y<=2n 使得 f(y)=0

• 把 [y...2n+y-1] 作为一段，它包含 n 个 0 和 n 个 1
• 剩余部分合并为一段
• 所以一共切成 3 段就可以

即只需要看第一个窗口就可以

如果第一个窗口 f(0) == 0 ，那么答案是 2，否则答案是 3