CSP-S 提高级 · CSP 2024 提高级第一轮 第 14 题

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

拿到题先别想冒泡排序，直接看相对位置：要把 k 个 1 挪到最右，最坏情况就是它们全在最左。每个 1 都要跨过右边所有的 0，一共 (n-k) 个 0，所以是 k 乘以 (n-k)。

最容易掉进的坑是选 B 那个 k×(k-1)/2。那是把 k 个 1 全部移到最左端（或把 0 移到最右端）时，它们之间互相交换产生的逆序对数量。但本题是移到最右端，1 和 1 之间不需要交换，只需要和 0 交换，所以 B 是典型的‘方向搞反’错误。

考点与概念

这道题考的是相邻交换与逆序对计数的结合，但和经典冒泡排序不同。核心概念很简单：一次操作只能换相邻两个字符，把一个 1 往右挪一格，就必须和它右边的一个 0 交换。因此，把一个 1 从当前位置移到最右边，它需要交换的次数，就是它右边有多少个 0。

命题视角

命题人专门挖了个坑：把“移到最左”和“移到最右”混在一起考。如果你脑子里只有“逆序对总数 = k×(k-1)/2”，很容易惯性选 B。其实 B 描述的是 k 个 1 彼此之间互相交换的次数（即它们全挤在一起时的内部逆序对），而本题问的是 k 个 1 和 (n-k) 个 0 之间的交换次数。命题人就是想看你是否分得清“同类元素交换”和“异类元素交换”。

思考心法

拿到题先想最坏情况：k 个 1 全在最左边，(n-k) 个 0 全在最右边，串长成 11…100…0。这时候每个 1 都要越过右边所有的 0 才能到最右。

• 最左边的第 1 个 1：右边有 (n-k) 个 0，要交换 (n-k) 次。
• 第 2 个 1：它右边仍然有 (n-k) 个 0（因为前面的 1 已经和那些 0 换过了，没减少 0 的数量），再交换 (n-k) 次。
• ……
• 第 k 个 1：同理，也是 (n-k) 次。

所以总次数 = k × (n - k)。

避坑指南

选项 B 的 k×(k-1)/2 是经典错误答案。它对应的是把 k 个 1 全部移到最左边（或把 0 移到最右边）时，1 和 1 之间产生的逆序对。本题方向反了，1 和 1 之间不用交换，只用和 0 交换，因此 B 一定不对。另一个易错点是忘记“最坏情况”意味着 1 全在最左，如果默认 1 已经分散，会算出更小的数，但题目明确问最坏情况，必须按极端分布算。

考频与趋势

“排列组合基础”在题库中非常高频，共 147 题，覆盖从 GESP 到 CSP 提高级、NOIP 等所有级别。2024 年有 40 题、2025 年有 43 题，说明这类计数与最值问题在最近两年是命题热点。而“双指针”只有 5 题，且近年每年稳定 1 题，说明纯指针技巧不是本题重点，本题更偏向组合计数。

预测

基于 2024-2025 年“排列组合”考题数量激增的趋势，未来这类“移动元素最坏交换次数”的题目仍会频繁出现，但可能会换皮：比如改成移动 0 到最左、或移动特定字符到中间某位置，甚至加入权重。只要抓住“最坏情况 = 目标元素全在一端，异类元素全在另一端”这一本质，就能快速秒杀。暂无足够依据预测更具体的变种形式，但方向一定是围绕“异类交换计数”展开。