Solution - P6155 修改

P6155 修改

随便交了一发竟然跑到了最优解！

不过这道题还是挺有思维含量的。

题意比较易懂，不再赘述。

首先可以发现一个性质：可以任意交换 $b$ 意味着可以任意交换 $a$ 。

既然如此，我们不妨将 $a,b$ 都排好序（从小到大）。现在我们来看 $a$ 数组中的元素。

如果 $a_i$ 是唯一的，那么一定不会操作它，也一定不会有数移到和他相同的值。

假如有 $a_j$ 移动到 $a_i$ ，代价是 $(a_i-a_j)\cdot b_x$ ，那么 $a_i$ 就要移动到 $x$ ，代价是 $(x-a_i)\cdot b_y$ 。但如果我们直接将 $a_j$ 移动到 $x$ ，距离相同，却可以少浪费一个 $b$ 。所以 $a_i$ 不移动更划算。

那么我们可以将所有出现过的元素都删除一个，剩下的都是必须挪动的元素。

然后我们可以发现最优方案中总移动距离一定是最少的。因为如果总移动距离不是最少的，那这种方案一定是某一种使总移动距离最少的方案在移动若干步得到的。

由于 $b$ 数组对最终答案的影响，我们应当让总移动距离最小的情况下让移动距离大的数移动距离更大一些，这样可以减少花费。

我给出的处理办法是：对 $a$ 从大到小循环，同时用一个栈维护能到达的数，每次都贪心地到达最近的点。这样可以减少跑得近的点的距离，增加跑得远的点的距离。

表述能力太差了捏，其实代码是很短的：

简洁易懂的代码

实现是非常容易的，主要还是考思维。