abc393 D

大意

题目大意是，给定01串，要使用左右交换把 1 聚拢到一起，问最小的交换次数

解法

感谢群友，这题用到的是中位数定理

alt

alt

官方解法：

每个 0 在最后要不就是在 1 区块左边，要不就是在右边。也就是说要么左边没有 1 ，要么右边没有 1。

每次有效交换必定是交换 01，结果将使得该 0 的左右 1 数量一个加一，一个减一，对其他 0 没有影响。

所以每个 0 都选择最省事的方法，哪边 1 少就去哪边。 详细证明如图，不想看了 alt alt