AT_abc393_d [ABC393D] Swap to Gather 题解
Pig_Eat_Earth · · 题解
AT_abc393_d [ABC393D] Swap to Gather 题解
题面翻译
英文版
题目描述
给定一个长度为 01串1。
你可以进行以下操作任意（可以为零）次：
- 选择一个整数
i(1\le i<N) ，并交换S 的第i 和第(i+1) 个字符。
找到使所有1连续的最少操作次数。
本题中，所有1连续当且仅当：
输入格式
共两行，第一行一个整数
输出格式
一行一个整数，表示答案。
数据保证
-
2\le N\le 10^5 -
-
-
## 思路 ### 前置知识 $\sum^n_{i=1}|x-a_i|(a_1\le a_2\le\dotsb\le a_n)$ 取最小值当且仅当： $$\begin{cases} x\in [a_\frac{n}{2},a_\frac{n+2}{2}] &\text{if } 2|a \\ x=a_\frac{n+1}{2} &\text{otherwise} \end{cases}$$ ### 思路 注意到，在最优方案中，所有`1`的相对位置都不变。因此，对于一个连续处左端点 $l$，第 $i(1\le i\le k)$（$k$ 为`1`的个数）个`1`会到位置 $l+i-1$。于是可得连续出左端点 $l$ 所对应的代价为： $$cost_l=\sum^k_{i=1}|p_i-(l+i-1)|=\sum^k_{i=1}|l-(p_i+i-1)|$$ 其中，$p_i$ 为第 $i$ 个`1`的初始位置。 我们可以 $O(n)$ 预处理出 $(p_i-i+1)$。根据**前置知识**可知，当 $l=\lfloor \frac{k}{2}\rfloor$ 时，$cost$ 取最小值。 另外，注意到 $\forall 2\le i\le k,p_i-p_{i-1}\ge 1$，因此 $(p_i-i+1)-[p_{i-1}-(i-1)+1]=p_i-p_{i-1}+1>0$，即 $(p_i-i+1)$ 单调递增，无需排序即可 $O(1)$ 求出中位数。 ### 解法 令 $pos_i=p_i-i+1$。 1. 预处理出 $p_i$、$pos_i$。 2. 将 $pos$ 的中位数代入 $cost$，求出答案。 ### 时间复杂度 显然为 $O(n)$。 ## AC Code ```cpp #include <bits/stdc++.h> #define int long long using namespace std; string s; int n, tot; vector<int> pos;
int cal(int pos){ int res = 0, cnt = 0; for(int i = 1; i <= n; ++ i) if(s[i] == '1') res += abs(pos + (cnt ++) - i); return res; }
signed main(){ cin >> n >> s; s = " " + s; for(int i = 1; i <= n; ++ i) if(s[i] == '1') pos.push_back(i - (tot ++)); cout << cal(pos[pos.size() >> 1]) << endl; }