第1题-阅览席并段校准 - problem_ide - CodeFun2000

登录查看题面

登录后即可查看完整题面内容。

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（蚂蚁机考题库），可解锁完整内容。

购买题库开通会员

解题思路

合法形态至多由一段连续的 $0$ 与一段连续的 $1$ 组成，因此一定可以写成 $0^*1^*$ 或 $1^*0^*$ （整串同色是这两种的特例）。

枚举分界位置 $p$ （ $0 \le p \le n$ ），把前 $p$ 个位置改成同一种字符、后 $n-p$ 个改成另一种字符。
用前缀和在 $O(1)$ 内计算两种改法的代价： $f_{01}(p)$ 表示前缀改成 $0$ 、后缀改成 $1$ 的翻转次数， $f_{10}(p)$ 则对调两种字符。
答案为所有 $p$ 上 $f_{01}(p)$ 与 $f_{10}(p)$ 的最小值。该过程本质是前缀和 + 枚举分界，线性扫描即可。

常见假解包括：只把整串改成全 $0$ 或全 $1$ ；或者只考虑 $0^*1^*$ 而漏掉 $1^*0^*$ 。

编辑器加载中…

输入

预期输出（选填）