「NOI2017」蔬菜
问题描述
小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。
在蔬菜仓库中，共存放有 $n$ 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各方面因素，设计合理的销售方案，以获得最多的收益。
在计算销售蔬菜的收益时，每销售一个单位第 $i$ 种蔬菜，就可以获得 $a_i$ 的收益。
特别地，由于政策鼓励商家进行多样化销售，第一次销售第 $i$ 种蔬菜时，还会额外得到 $s_i$ 的额外收益。
在经营开始时，第 $i$ 种蔬菜的库存为 $c_i$ 个单位。
然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过聪明的小 N 已 经计算出了每个单位蔬菜变质的时间：对于第 $i$ 种蔬菜，存在保鲜值 $x_i$，每天结束时会 有 $x_i$ 个单位的蔬菜变质，直到所有蔬菜都变质。（注意：每一单位蔬菜的变质时间是固 定的，不随销售发生变化）
形式化地：对于所有的满足条件 $d\times x_i \leq c_i$ 的正整数 $d$ ，有 $x_i$ 个单位的蔬菜将在 第 $d$ 天结束时变质。
特别地，若 $(d−1)\times x_i \leq c_i < d\times x_i$ ，则有 $c_i−(d−1)\times x_i$ 单位的蔬菜将在第 $d$ 天结束时变质。
注意，当 $x_i = 0$ 时，意味着这种蔬菜不会变质。
同时，每天销售的蔬菜 . 总量也是有限的，最多不能超过 $m$ 个单位。
现在，小 N 有 $k$ 个问题，想请你帮忙算一算。每个问题的形式都是：对于已知的 $p_j$，如果需要销售 $p_j$ 天，最多能获得多少收益？
输入格式
第一行包含三个正整数 $n,m,k$，分别表示蔬菜的种类数目、每天能售出蔬菜总量上限、小 N 提出的问题的个数。
接下来 $n$ 行，每行输入四个非负整数，描述一种蔬菜的特点，依次为 $a_i,s_i,c_i,x_i$ ， 意义如上文所述。
接下来 $k$ 行，每行输入一个非负整数 $p_j$ ，意义如上文所述。
输出格式
输出 $k$ 行，每行包含一个整数，第 $i$ 行的数表示第 $i$ 个问题的答案。
样例输入
2 3 2
3 3 3 3
2 5 8 3
1
3
样例输出
16
27
提示
$n \leq 10^5, m \leq 10, p_j \leq 10^5, 0 < a_i,c_i \leq 10^9 , 0 \leq s_i,x_i \leq10^9 $
首先这题容易想到费用流，即将每天看成一个点，从源点往每天连边，容量为$m$，然后对每种蔬菜，将他拆成$\lceil \frac{C}{x}\rceil$天卖出，每天卖$x$，然后最后一天处理一下$a_i+s_i$即可。
然而费用流显然是过不了大数据的。正解考虑贪心。
我们考虑一个朴素的贪心，如果能卖菜的天数确定，那么将蔬菜的权值从大到小排序，用堆维护，然后一个一个卖，然后显然如果要卖这个蔬菜，就应该安排到他最后能卖的一天卖，这个时间由$\lceil \frac{C}{x}\rceil$给出，那么我们就将他安排一单位到这一天卖，其他的放回堆中。如果这一天已经卖了$m$个，那就要往前找到第一个没有卖到$m$个的位置。这个可以用并查集来实现，如果某一天已经卖了$m$个，就将他和前一天合并。这样并查集的根就是他往前第一个还能卖菜的位置。
然后我们考虑处理多组询问，实际上，当我们求出了$p$的卖菜方案$S_p$之后，$p-1$的卖菜方案$S_{p-1}$一定是$S_p$的一个子集，因为$S_p$中的所有元素都可以在前$p-1$天卖出。因此只需要从$S_p$中取$(p-1)m$个元素就行了。
因此我们只需要处理出$p_{max}$的答案，然后记录下$ans[i]$表示选$i$个蔬菜的最优答案就行了。
代码：
1 |
|