题意

给出一段由'.'和'*'组成的字符串，如果'*'的左边为'.'，则可以将'*'向左边移动一格，代价为$1$，往右亦然。现在要求出使得所有的'*'变为连续的一个串，求最小的代价。如**..*. $\rightarrow$ ..***.。

思路

拿到这一题，感觉上应该是个构造，寻找到某个点，这个点能够使得左右的'*'都移动过来，合为一个串，这样是最优的。但是这个点一时间不太能知道怎么求，于是考虑枚举。

我们枚举每一个点作为一个“聚拢点”，两边的'*'都往这个点靠过来形成子串。这时，我们需要$O(1)$或者$O(logN)$得到两边靠过来形成子串的代价。

我们可以通过拆分为求左边的*靠过来，和右边的'*'靠过来简化问题，并使用前缀和来帮助我们。有：

$$pre[i] = pre[i - 1] + sum[i] * [str[i] = * ]$$ $$suf[i] = suf[i + 1] + (sum[n] - sum[i - 1]) * [str[i] = * ]$$

其中，$sum[i]$为前缀和，代表$[1, i]$种有多少个'*'。$pre[i]$为$i$左边所有的'*'形成以$i$为结尾的子串所需代价，$suf$是右边的'*'形成子串的对应代价。

由此，我们可以知道，最终答案为：

$$ans = min(ans, pre[i] + suf[i + 1])$$

这种方法比较直观，还有另外一种贪心的方法。

我们转为数学表达式，实际上，题目要求：

$$cost = min(|s_1 - x| + |s_2 - (x + 1)| + |s_3 - (x + 2)| + \dots)$$

$s_i$为第$i$个'*'所处在的位置下标，$x$是最终答案形成子串的起始点。

我们可以构造，$B_i = s_i - (i - 1)$，原式转化为：

$$cost = min(|B_1 - x| + |B_2 - x| + |B_3 - x| + \dots)$$

这样，整个式子就直观了很多，我们可以知道，只要取$x$为$B_i$的中位数，就可以得到最小值。

这一题和$AtCoder$上的这一题是一样的：C - Linear Approximation

到此，就可以使用这些方法来解决这道题。

结尾

之前开了两三场$vp$的题目，还没补，在学了在学了（（（