Logo WF_wxl 的博客

博客

#770-出题人题解

avatar WF_wxl 2026-10-11 16:47:54

个人认为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}) $。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。

WF_wxl Avatar
菜
活跃度 近 53 周
查看全年