CSP-S 2024 第一轮 第14题：设有一个长度为n的θ1字符串，其中有k个1，每次操作可以交换相邻两个字符。在最

题目

设有一个长度为 $n$ 的 $01$ 字符串，其中有 $k$ 个 $1$。每次操作可以交换相邻两个字符。在最坏情况下将这 $k$ 个 $1$ 移到字符串最右边所需要的交换次数是多少？

选项

• A. $k$
• B. $k\times (k-1)/2$
• C. $(n-k)\times k$
• D. $(2n-k-1)\times k/2$

答案

C

题解

选 C：$(n-k)\times k$。

要把所有 $1$ 移到最右边，就要让每个 $1$ 越过它右侧的所有 $0$。每次交换相邻的 10 为 01，恰好让一个 $1$ 越过一个 $0$。

最坏情况是所有 $1$ 都在左边，所有 $0$ 都在右边： $$ \underbrace{11\cdots1}_{k\text{ 个}} \underbrace{00\cdots0}_{n-k\text{ 个}} $$

此时每个 $1$ 都要越过 $n-k$ 个 $0$，共有 $k$ 个 $1$，所以需要 $$ \boxed{k(n-k)} $$ 次交换。