- D. A and B
- E. Hidden Knowledge of the Ancients
Codeforces Round 1054 (Div. 3)
D. A and B
参考了 Tutorial
题意很简单，（总结后）就是将所有的字符 a 或者所有的字符 b 汇集到一起。那么对于每种字符分别考虑位置聚到一起的代价，选择小的就是答案。
Let the target be to make all occurrences of one letter contiguous. Do it for both letters and take the minimum.
Fix a letter \(c\in{a,b}\) and let its positions be \(p_0<p_1<\dots<p_{m-1}\). If we place these \(m\) copies into a consecutive block starting at some index \(L\), the number of adjacent swaps needed is $ \sum_{i=0}^{m-1} \bigl|, p_i - (L+i) ,\bigr| ;=; \sum_{i=0}^{m-1} \bigl|, (p_i - i) - L ,\bigr|$
Set \(b_i=p_i-i\). The function \(\sum_i |b_i-L|\) is minimized when \(L\) is a median of \({b_i}\). Hence the optimal cost to cluster all \(c\)'s is
$ \operatorname{cost}(c) = \sum_{i=0}^{m-1} \bigl|, b_i - \operatorname{med}(b) ,\bigr|, \quad \text{where } b_i = p_i - i.$
The answer is \(\min(\operatorname{cost}(a),\operatorname{cost}(b))\).
This counts the minimal number of adjacent swaps because each swap reduces the sum of pairwise inversions between the two types by exactly \(1\), and aligning to a consecutive block achieves the minimum. The algorithm computes positions, builds \(b_i\), takes the median, and sums absolute deviations — all in linear time after positions are known.
The time complexity is \(O(n)\).
在代码实现中，最终计算的是 val += abs(v[pos] - v[i]) - abs(pos - i);。这样的写法和题解的描述是等价的！
中位数的选取即为 k = m / 2 位置上的数 p[k] - k
题解公式为 \(cost(a) = \sum_{i = 0}^{m - 1} |b_i - b_k| = \sum_{i = 0}^{m - 1} |(p_i - i) - (p_k - k)|\)
代码对应的公式为 \(val = \sum_{i = 0}^{m - 1} (|p_i - p_k| - |i - k|)\)
对于本题，这两个式子是对应成立的
代码：Qiansui_code
E. Hidden Knowledge of the Ancients
参考链接
- 双指针做法：https://zhuanlan.zhihu.com/p/1954707609866208306
- 容斥做法：https://www.cnblogs.com/cjiaw/articles/19148932