个人认为A>B。
首先,题目条件等价于存在一个$ x $,满足:
- $ \forall 1 \le i \le n , a_i \ge x $
- $ \forall 1 \le i \le m , b_i \le x $
于是,调整的代价为:
- 对于$ a $:$ \sum_{a_i < x} (x-a_i) $
- 对于$ b $:$ \sum_{b_i > x} (b_i-x) $
总代价为$ \sum_{a_i < x} (x-a_i) + \sum_{b_i > x} (b_i-x)$。
求这玩意的最小值。
感性理解一下,这东西似乎是可以二分求解的。我知道你看不出来,我们来证明一下。
令总代价为$ f(x) $,算一下差分:
$ f(x+1)-f(x)=count(a_i \le x)-count(b_i > x) $
(其中,$ count() $函数表示满足要求的数的个数)。
含义为,每把$ x $增加$ 1 $,$ a $中每一个原来$ \le x $的$ a_i $都会增加$ 1 $的贡献,而$ b $中每一个原来$ > x $的$ b_i $都会减少$ 1 $的贡献。
而随着$ x $的增大,$ \le x $的数会越来越多(即$ count(a_i \le x) $单调不降),而$ > x $的数会越来越少(即$ count(b_i > x) $单调不增)。
于是我们证明了$ f(x+1)-f(x) $单调不降。于是$ f(x) $是一个下凸函数。
我们直接二分,找出第一个$ f(x+1)-f(x) \le 0 $的位置即为答案。
时间复杂度$ O((n+m)log10^{18}) $。
