题解

思路

每次操作翻转两枚硬币，所以 1 的个数奇偶性不变；个数为奇数时一定无解。

做法

若 1 的个数为 $0$，答案为 $0$；若不少于 $4$，或恰有两个但位置不相邻，就能每次消去两个 1，下界“个数除以二”可以达到。

只剩“恰有两个相邻的 1”需要特判：$N=3$ 时唯一可操作的位置对无法消去它们，答案为 $-1$；$N=4$ 且字符串为 0110 时最少需要 $3$ 次；其余情况可以借助相邻 1 同侧或远端的辅助位置用 $2$ 次完成。

复杂度

逐个字符串统计 1 并检查是否相邻即可，时间复杂度为所有字符串总长度的 $O(\sum N)$，额外空间复杂度为 $O(1)$。