题解：CF2085F1 Serval and Colorful Array (Easy Version)

· · 题解

Sol

下文中答案表示 k 个点到某个中心的距离之和，真正的答案需要减去 \displaystyle\sum_{i=1}^n\left|i-\left\lfloor\frac{k+1}{2}\right\rfloor\right|。

考虑 F1 做法，假设选定一个点在 i，并且以这个点为中心，i 左边第一个颜色为 j 的位置到 i 的距离为 l_j，右边第一个颜色为 j 的到 i 的距离为 r_j。

此时最优方案一定是 i 两侧 l_j 和 r_j 各选一半。

令 c_j=r_j-l_j，将 c 排序后答案就是 \displaystyle\sum_{i=1}^nl_j+\sum_{i=1}^{\left\lfloor\frac{k+1}{2}\right\rfloor}c_j。

时间复杂度：O(n^2)。

引理：不用考虑在 i 两侧各选一半 l_j 和 r_j，一定能统计到最优解。

证明：由仓库选址问题可知如果选的中心不在正中间那么答案一定不优，且该方案一定能统计到最优解。

那么事情就变得简单了，答案变成了 \displaystyle\sum_{i=1}^n\min(l_i,r_i)，感觉还是不太好做，对于每一个 \min(l_i,r_i) 观察可得每当 i 加上 1，\min(l_i,r_i) 变化的绝对值不超过 1，观察变化规律可以发现每次都是区间加一个等差数列，也就是一个二维差分，那么就做完了。

时间复杂度：O(n^2)。

Code

F1。

F2。