只讲贪心做法。

一、反悔贪心

考虑如何使选的星星总数多一。显然，有如下几种方式：

• 选一个之前没选过的位置 \(i\)，答案加上 \(a_i\)。

• 选一个之前选过一次的位置 \(i\)，答案加上 \(b_i-a_i\)。

• 对于一个之前选过一次的位置 \(i\)，再找到一个没有选过的位置 \(j\)，反悔掉 \(i\)，并选两次 \(j\)，答案加上 \(b_j-a_i\)。

• 对于一个之前选过两次的位置 \(i\)，再找到一个没有选过的位置 \(j\)，反悔掉 \(i\) 的第二次选择，并选两次 \(j\)，答案加上 \(b_j-(b_i-a_i)=b_j-b_i+a_i\)。

总结一下，我们需要分别维护 \(a_i,b_i,-a_i,a_i-b_i,b_i-a_i\) 的最值，使用五个堆即可。但是每个策略可能会对多个堆进行修改，比较复杂，不推荐。

时间复杂度 \(O(n\log n)\)。

二、直接贪心

考虑每次选两个星星，那么我们需要权衡的是选 \(a_i+a_j\) 还是 \(b_i\)。

定义：\(2\) 物品表示根据以上选择方式，一次用掉 \(b_i\)，对答案贡献为 \(2\) 的物品，剩下的都是 \(1\) 物品（如果其 \(b=2\)，会分成 \(a\) 和 \(b-a\) 两次选）。

开两个堆，存储 \(1\) 物品和 \(2\) 物品，然后每轮选择进行如下过程：

• 记录每个数是作为 \(2\) 物品被扔掉还是 \(1\) 物品。然后对于每个堆，把所有不合法的扔掉。

• 取出 \(1\) 堆的最小值和次小值 \(a_{mn},a_{se}\) 和 \(2\) 堆的最小值 \(b_{mn}\)（若不存在视为 \(+\infty\)）。

• 若 \(a_{mn}+a_{se}\le b_{mn}\)：记录下每个数被选的次数，令 \(a_{mn},a_{se}\) 对应的 \(cnt\to cnt+1\)，并标记为作为 \(1\) 物品使用。若此时 \(cnt=1\)，说明选择的是 \(a\)，再将 \(b-a\) 扔进去。然后把 \(b_{mn}\) 扔回去（如果是 \(+\infty\)，忽略）。

• 否则：使用 \(b_{mn}\)，设置其 \(cnt=2\)，作为 \(2\) 物品被使用。然后将 \(a_{mn},a_{se}\) 塞回去。

这样选择方案就输出 \(cnt\) 即可。

但是这样做有一个问题：如果 \(w\) 是奇数怎么办。此时我们可以加入一个值和编号都为 \(0\) 的 \(1\) 物品进去，并标记 \(cnt=1\)，这样它就只会被用一次。

时间复杂度 \(O(n\log n)\)。

Code