「Codeforces 1214F」Employment
题意
有一个大小为 \(m\) 的环，还上有 \(n\) 个点有工作单位，并且有 \(n\) 个点上住着一个人。你需要为每个人分配一个工作单位，使得所有人到工作单位的距离之和最短。输出一个方案。
\(m\le 10^9,n\le 2\times 10^5\)
题解
下面的数组都从 \(0\) 开始标号。先将 \(a,b\) 数组分别从小到大排序，然后把 \(b\) 数组变成 \(b_0,b_1,b_2,\cdots,b_{n-1},b_0+m,b_1+m,\cdots,b_{n-1}+m,b_0+2m,b_1+2m,\cdots,b_{n-1}+2m\)，把 \(a\) 数组变成 \(a_0+m,a_1+m,a_2+m,\cdots,a_{n-1}+m\)。
考虑贪心，显然两个人的路径不能“交叉”，所以一定是小的和小的匹配，大的和大的匹配。问题变成了求 \(\min\limits_{0\le x\le 2n} \sum\limits_{i=0}^{n-1} |a_i-b_{i+x}|\) 的值。
记 \(ans_x=\sum\limits_{i=0}^{n-1} |a_i-b_{i+x}|\)，把绝对值拆开，则变成了
\[\begin{aligned}ans_x&=\sum\limits_{i=0}^{n-1} |a_i-b_{i+x}| \\ &=\sum\limits_{i=0}^{n-1} ([a_i > b_{i+x}]a_i-[a_i < b_{i+x}]a_i-[a_i > b_{i+x}]b_{i+x}+[a_i < b_{i+x}]b_{i+x})\end{aligned}\]
记 \(sa_{x}=\sum\limits_{i=0}^{n-1} ([a_i > b_{i+x}]a_i-[a_i < b_{i+x}]a_i),sb_{x}=\sum\limits_{i=0}^{n-1} ([a_i < b_{i+x}]b_{i+x}-[a_i > b_{i+x}]b_{i+x})\)。考虑单独计算。
我们将 \(sa\) 差分，发现 \(sa_x-sa_{x-1}=\sum\limits_{i=0}^{n-1} ([a_i > b_{i+x}]a_i-[a_i < b_{i+x}]a_i-[a_i > b_{i+x-1}]a_i+[a_i < b_{i+x-1}]a_i)\)，发现若 \(a_i \le b_{i+x-1} \le b_{i+x}\) 或 \(b_{i+x-1} \le b_{i+x} \le a_i\) 时，这个式子恰好为 \(0\)，只有当 \(b_{i+x-1} < a_i < b_{i+x}\) 时，这个式子的值为 \(-2a_i\)，而这个 \(x\) 又是唯一的。于是对于每个 \(a_i\) 求出这个唯一的 \(x\)，在差分数组上直接修改即可。
我们依次考虑每个 \(b_i\)，发现当 \(x\) 小于某个值时，\(b_i\) 对 \(sb_x\) 的贡献是负的，否则是正的。于是我们求出这个值，然后区间加贡献即可。这个也可以用差分简单的实现。
发现求 \(sa_x,sb_x\) 在实现的过程中都需要差分，不需要分开计算。
时间复杂度 \(O(n\log n)\)。
代码
1 |
|
