AT_abc393_d [ABC393D] Swap to Gather 题解

题面翻译

英文版

给定一个长度为

N

的01串

S

。保证

S

中至少包含一个1。

你可以进行以下操作任意（可以为零）次：

找到使所有1连续的最少操作次数。

本题中，所有1连续当且仅当：

\exists l,r(l,r\in \N\land l,r\in \left[1,n\right]),\forall 1\le i\le n,S_i=\left[l\le i\le r\right]

共两行，第一行一个整数

N

，第二行一个字符串

S

，意义如上。

一行一个整数，表示答案。

\sum^n_{i=1}|x-a_i|(a_1\le a_2\le\dotsb\le a_n)

取最小值当且仅当：

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; } ```