本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$ 数组中的前驱或后继。

$a$ 值大于 $a_i$ 的所有卖部都必须卖给小 $b$，这个改变不了，所以就在所有可以自由选择卖给谁的卖部的 $b$ 数组里面选择 $a_i$ 的前驱，后继分别作为可以自由卖的卖部中卖给小 $b$ 的最大值，分别取最优值。

如果做到这一步结束了，并且是在赛时，那么恭喜你 FST 了。

还有一种可能，那就是只选择 $a$ 值大于 $a_i$ 的卖部卖给小 $b$，也就是可以自由卖的全都给小 $a$。

就这个东西让我 vp 的时候吃了 5 次罚时。

细节比较多。

CF 提交记录