CF802O April Fools' Problem (hard)

题意 ： 给定两个长度为 的数列 和 ，并给定 ，要求选出 和 ，满足：

，。 。

最小化 的值。

，时限 。

---

看到 ，猜想这是凸的。由于有费用匹配做法，正确性显然，而且斜率也均为整数。

于是考虑 有负数时如何快速求解没有 限制的问题。考虑贪心。

从 到 考虑 ，这样能匹配的 会逐渐变多。

有两种决策：

• 加入当前的 ，挑一个目前能匹配的最大的 。

• 用当前的 去替换前面最小的 。

用堆维护即可，复杂度 。