abc393题解集合
文章同载于：
fyy 是一个非常珂愛的女孩子。
fyy 认为一个 \(01\) 序列中如果所有 \(1\) 都是连续的，那么这个序列很珂愛。fyy 想通过有限次操作使得一个序列变得珂愛。对于每次操作，她只能交换两个相邻的数。
fyy 问妳最少的操作次数是多少？
讲一下一个假的做法。看到这个题立马想到 ABC 以前的一道题，把所有的 \(1\) 都往最左边的一个移动。错误很显然。
这个问题很迷惑，实际上所有 \(0\) 都是没用的，只需考虑 \(1\)。
钦定最优情况一定是选择一个 \(1\) 作为合并的起始点，将其两边的 \(1\) 逐渐合并。如果最优情况可能是 \(0\) 类似讨论即可。
形式化的说，序列中给出了 \(M\) 个 \(1\)，其中第 \(i\) 个 \(1\) 的位置是 \(X_i\)。选定第 \(k\) 个 \(1\)。
求 \(\sum\limits_{i=1}^{k-1} \left[X_k-X_i-(k-i)\right]+\sum \limits_{i=k+1}^{M} \left[X_i-X_k-(i-k)\right]\) 的最小值（其实上式也可写成绝对值形式）。
不妨考虑一个子问题。给定 \(M\) 个数轴上的点 \((X_1,X_2,\dots,X_M)\)。设 \(x\) 为任意一点。求 \(\sum\limits_{i\in[1,M]}|x-X_i|\) 的最小值。运用几何直观，显然当且仅当 \(x\) 在中间两点所成区间（包含区间断点）内时取得最小值（如果 \(M\) 为奇数那么 \(x=X_{mid}\)，\(mid\) 为 \(1\sim M\) 的中间值 \(\left\lfloor \frac{M}{2}\right\rfloor+1\)）。
对此的证明可以翻开你的人教版七年级第一章有理数的各种教辅资料，应该都有这种题目。
类似于刚才的问题，我们注意到 \(\sum \left|k-i\right|\) 和 \(\sum\left|X_k-X_i\right|\) 都可以在 \(k=\left\lfloor \frac{M}{2}\right\rfloor+1\) 时取得最小值（原因是我们将其抽象转换成刚才的问题）。
于是我们解决了这个问题。下面形式化做法：
- 找出所有点 \((X_1,X_2,\dots,X_M)\)，找出中间点为合并初始点，也就是 \(X_{\left\lfloor \frac{M}{2}\right\rfloor+1}\)。这个点记为 \(X_{mid}\)。
- 求出 \(\sum\limits_{i=1}^{mid} \left[X_{mid}-X_i-(k-i)\right]+\sum \limits_{i=mid+1}^{M} \left[X_i-X_{mid}-(i-k)\right]\) 的值。
下面是代码：
1 | int main() |