CF1801B 题解

__vector__ · 2023-03-23 18:06:58 · 题解

纪念一下第一次比赛状态搞出 Div.2 ABCD 正解，虽然只是 vp。

题解

设第一个朋友为小 a，第二个为小 b。

很自然地想到枚举小 a 得到的最贵礼品的价值。

于是先将卖部按照 a_i 值升序排列。

然后枚举小 a 得到的最贵礼品所在的卖部，设当前枚举到第 i 个卖部。

显然，a 值大于 a_i 的所有卖部必须卖给小 b。

而 a 值小于等于 a_i 的所有卖部，除了当前卖部 i，都可以自由选择卖给小 a 还是小 b。

为了让卖给小 b 的最大价值最接近小 a 得到的最大价值即 a_i，应尽可能让卖给小 b 的最大价值等于 a_i 在所有可以自由选择卖给谁的卖部的 b 数组中的前驱或后继。