自动搬运

查看原文

来自洛谷，原作者为

	CJY 小升初蒟蒻||/article/ugxlm066/team/87748||没有一根棒棒糖解决不了的事情，如果有，就再来一根||最后在线时间：2025年8月24日20时21分

搬运于2025-08-24 23:17:21，当前版本为作者最后更新于2025-07-20 15:30:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官解讲得不太清楚，特来补一篇。

思路

当 $b_i \ge \sum\limits_{j=1}^{i-1} b_j$ 时，$s_i=a_i \times b_i=a_i+a_i \times (b_i-1)$，所以设权值为 $a_i \times (b_i-1)$。

然后将 $b$ 排序，记得用结构体绑定 $a,b$ 再进行排序。

设 $k$ 为当前 $b_i$ 的总和，接下来从 $\min(k,b_i)$ 开始向前枚举，避免重复计算。

我们设 $f_i$ 为当前已选同学的 $b_i$ 之和为 $i$ 时，能获得的最大额外权值和，动态转移方程过于明显，没什么好讲的：

然后更新总礼物价值 $k \gets k+b_i$。

结果就为 $\left(\max\limits_{i=1}^{5 \times 10^6}f_i\right)+\sum\limits_{i=1}^na_i$，$\sum\limits_{i=1}^na_i$ 就是把 $a_i+a_i \times (b_i-1)$ 中的 $a_i$ 加上，因为我们设的权值是 $a_i \times (b_i-1)$。

注意要开 long long，$f$ 的范围要开到 $5 \times 10^6$ 而不是 $5 \times 10^5$！

有问题请指出！