A. Shift Sort

问题描述

给定一个长度为 $n$ 的二进制字符串 $s$。你可以执行以下操作任意次数（包括零次）：

• 选择三个索引 $1 \leq i < j < k \leq n$，并将 $s_i, s_j, s_k$ 处的值向右或向左循环移位。

例如，对于字符串 $110110$：

• 如果你选择 $i=1, j=2, k=3$ 并执行右移，字符串变为 $011110$。
• 如果你选择 $i=4, j=5, k=6$ 并执行左移，字符串变为 $110101$。

你的任务是确定将二进制字符串按非递减顺序（所有 $0$ 在所有 $1$ 之前）排序所需的最少操作次数。

题解

关键观察

1. 操作效果：每次操作允许你循环移动三个元素，这可以用来将一个 ‘0’ 移动过两个 ‘1’，反之亦然。
2. 排序目标：目标是将所有 ‘0’ 移动到前面，所有 ‘1’ 移动到后面。
3. 最优策略：最少操作次数等于不在正确位置的 ‘0’ 的数量。每次操作可以交换一对 ‘0’ 和 ‘1’。

提交链接