题解

思路

对值 $x$，四种有意义的最终代价为：不操作 $x$；只减半 $h(x)=\lceil x/2\rceil$；只减法 $s(x)=\max(x-b,0)$；两种都做 $d(x)=\max(\lceil x/2\rceil-b,0)$。两种都做时先减半再减法不会劣于反序。

子任务 1

每个元素枚举“不做、只减半、只减法、两种都做”四种状态，递归统计两类操作数，复杂度 $O(4^n)$。

子任务 2

令 dp[p][q] 表示处理当前前缀且用了 $p,q$ 次两类操作时的最小和。每个元素进行四种转移，时间复杂度 $O(nk_1k_2)$，空间复杂度 $O(k_1k_2)$。

子任务 3

将数组降序排序。交换论证表明：若恰有 $c$ 个元素同时使用两种操作，则它们一定可以取前 $c$ 大；其后恰有 $k_1+k_2-2c$ 个元素使用一种操作，也一定可以取接下来的这些最大元素。

枚举

先把所有“只用一种”的元素暂定为减半。对其中元素 $x$，把操作改为减法引起的代价变化为 $s(x)-h(x)$；选择其中最小的 $k_2-c$ 个变化量即可。用 nth_element 在线性期望时间内选出它们。

前缀和可在 $O(1)$ 时间取得同时操作段、单操作段和不操作后缀的基础代价。所有枚举中参与选择的元素总数为 $O(n^2)$。

做法

1. 降序排序并预处理 $x,h(x),s(x),d(x)$ 的前缀和。
2. 枚举同时使用两类操作的元素数 $c$。
3. 对接下来单操作段的 $s(x)-h(x)$ 做线性选择，累加最小的 $k_2-c$ 个。
4. 更新最小答案。

正确性证明

$h,s,d$ 相对“不操作”的收益都随 $x$ 单调不减。对两个值 $x\ge y$，逐段检查 $x<b$、$b\le x<2b$、$x\ge2b$ 可得：把较多操作从 $y$ 交换给 $x$ 不会使总和增大。因此存在最优解使双操作元素为降序前缀，单操作元素紧随其后。固定这两个集合后，所有单操作元素先取减半；每把一个改成减法只会独立增加 $s(x)-h(x)$，选最小的规定数量显然最优。枚举覆盖了所有可行双操作数量，所以所得全局最小值正确。

复杂度

满分算法期望时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$；全文件按各测试规模分别计算。中档为 $O(nk_1k_2)$，小档为 $O(4^n)$。