橙子！

子任务 1：枚举第一个人购买的橙子集合。对每个大小为 $K$ 的集合，直接计算满意度并取最大值。时间复杂度为 $O(N2^N)$，空间复杂度为 $O(N)$。

完整解法：假设第二个人买下所有橙子，满意度为 $\sum_{i=1}^N b_i$。将第 $i$ 个橙子改由第一个人购买，满意度的变化量为 $a_i-b_i$。

令 $c_i=a_i-b_i$。问题变为恰好选择 $$ 个差值，使其总和最大。将差值降序排序，选择最大的 个。若某个未选值大于某个已选值，交换它们就能增大总和，因此这种选择是最优的。相等的值可以任意选择。

设排序后 $c_1\geq c_2\geq\cdots\geq c_N$，答案为

$$\sum_{i=1}^N b_i+\sum_{i=1}^K c_i$$

必须恰好选择 $K$ 个橙子，即使某些被选中的差值为负数，也不能跳过。

每个用例的时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。答案及计算中的和的绝对值不超过 $2\times10^{14}$，差值的绝对值不超过 。应使用 64 位整数存储总和。

Solution written by GPT