双语题解

zhouyuhang · 2023-02-20 12:06:15 · 题解

这是一篇双语题解。

Suppose we have determined the positions of dogs, we could know the coefficients (means |x-y|) of each position. According to the Rearrangement Inequality, we can calculate the contribution of dogs and cats separately in O(n).

By using Simulated Annealing and a few dirty tricks, we can solve the problem easily in 1900ms.

In the SA, we have a permutation p of 1\sim (n+m), which the first n elements represent the positions of dogs, and the rest of them represent cats. Every time we randomly choose two indices i\in [1,n],j\in [n+1,n+m] then swap p_i,p_j. You can see more details in code from my friend.

假设我们已经确定了狗的位置，我们可以知道每个位置的系数（意味着 |x-y|）。根据重排不等式，我们可以 O(n) 分别计算狗和猫的贡献。

通过使用模拟退火和一些平凡的技巧（比如卡时），我们可以在 1900ms 内轻松解决问题。

在退火中，我们有一个 1\sim (n+m) 的排列 p，其中前 n 个元素表示狗的位置，其余元素表示猫的位置。每次我们随机选择两个下标 i\in[1,n],j\in[n+1,n+m]，然后交换 p_i,p_j。可以在 来自我朋友的代码 中查看更多详细信息。