abc 393 D 题解
da_ke
·
2025-02-16 09:52:05
·
题解
注：本文涉及大量推导，如果读者发现谬误请批评指正！
Solution
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\limits_{i\in [1,M]} |k-i| 为定值：
于是我们的这个问题和子问题的取最小值的条件是类似的。所以我们可以找到一个使得原式取得最小值的点，即为 $X_{\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]$ 的值。
### Code
下面是代码：
```cpp
int main()
{
int N; string S;
cin>>N>>S;
S=' '+S;
int mid,M=0,cnt=0;
rep(i,1,N)
if(S[i]=='1') M++;
rep(i,1,N)
if(S[i]=='1')
{
cnt++;
if(cnt==M/2+1){mid=i; break;}
}
M=M/2+1;
ll ans=0; cnt=0;
rep(i,1,mid-1)
if(S[i]=='1')
{
cnt++;
ans+=mid-i;
ans-=(M-cnt);
}
cnt=M;
rep(i,mid+1,N)
if(S[i]=='1')
{
cnt++;
ans+=i-mid;
ans-=(cnt-M);
}
cout<<ans<<endl;
}
// 路虽远行则将至，事虽难做则必成。
// 代码省略缺省源（所以直接交上去会 CE），完整代码放在底下。
```
AC 记录：<https://atcoder.jp/contests/abc393/submissions/62799606>
### 一个补充证明
我们刚开始钦定了选 $1$ 是根据**直觉**的。下面详细说明 $0$ 的情况
如果选的 $0$ 的点为 $X_0$，在这个点左侧有 $l$ 个 $1$，右侧有 $M-l$ 个 $1$。$M$ 个 $1$ 点为 $(X_1,X_2,\dots,X_M)$。
类似的列出最终的式子：
$$\sum\limits_{i\in [1,l]} [X_0-X_i-1-(l-i)]+\sum\limits_{i\in [l+1,M]} [X_i-X_0-1-(i-l-1)]$$
这表明，如果 $M$ 为偶数，选 $0$ 也能得到最小值；若为奇数，则得不到最小值。