均分 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