CF2085F1 题解

前言

最近状态好差好差好差好差。。。。。。好难受

思路

最小化交换次数这种东西嘛，一个常见的结论是维持中位数的位置不变，然后把两边的东西都聚拢到中位数的位置，证明可以用调整法。具体到这个题里，假设我们知道了最后要选哪些数，就可以直接算出答案为 $\sum\limits_{i=1}^k |p_i-p_x|-|x-i|$，其中 $x$ 是中位数的排名（即 $\frac{k}{2}$，容易证明向上取整和向下取整无所谓，不影响正确性），$p_i$ 代表第 $i$ 个选择的数的下标。

既然这个答案形式跟中位数强相关，我们直接枚举中位数在哪个下标 $x$ 然后对所有答案取 $\min$。那么现在的目标是要在 $x$ 左边选一半，右边选一半，凑出 $1\sim k$ 内的所有数。

首先，上面贡献式子右边不带 $p$ 的那一项是独立的，只需要关心左边。容易发现对于每个值 $c$，如果其在最后的答案中在 $x$ 左边，那么此时 $p_c$ 必定为满足 $a_i=c,i<x$ 的最大 $i$，否则为满足 $a_i=c,i>x$ 的最小 $i$。设这两个位置分别为 $l_c$ 和 $r_c$。现在需要干的事情在 CF2140D 里亦有记载，先全都钦定选 $l$，然后调整一个 $l$ 为 $r$ 的代价是 $(r-x)-(x-l)=l+r-2x$，直接对所有 $l_c+r_c-2x$ 排序然后取前 $\frac{k-1}{2}$ 小的即可。