• 周五. 12月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[NOI2017]蔬菜

admin

11月 28, 2021

Problem

你有 (n) 种疏巨,每销售一个单位第 (i) 种疏巨,获利 (a_i) 元。第一次销售额外获利 (s_i) 元。开始时有 (c_i) 单位,每天会变质 (x_i) 份。每天你最多可以销售 (m) 单位疏巨。

(k) 组询问,每次询问销售 (p) 天,获利最大值。

Sol

(m orz~mathtt{color{black}Scolor{red}{yksykCCC}})

首先第一下很容易会想贪心:每天选择剩余获利最多的疏巨销售,这样子貌似很优秀。但反例也不难举出来:两种疏巨,一种收益很低,但变质很快;一种收益很高,但不会变质(或变质很慢),询问的天数很长,这样我们肯定先选变质快的,再慢慢悠悠地选择不变变质的,这样在总量上会变多。

顺着这个角度思考,发现如果天数短的话肯定优先选择收益高的疏巨(因为肯定销售不完)。

我们会发现:对于一种疏巨,满足销量的前提下,尽可能迟地销售,这样就可以为其它需要早早销售的疏巨腾出空间。

假设第 (i) 种疏巨在销售 (d_i) 份时,能够允许的时间为 (t_i),可以得到两个方程

[egin{cases}
egin{aligned}
t_igelceilfrac{d_i}{m}ceil
end{aligned}\
x_i(t_i-1)+d_ile c_i
end{cases}
]

解得

[lceilfrac{d_i}mceille t_ilelfloorfrac{c_i-d_i}{x_i}floor+1
]

我们希望其能尽可能迟地销售,则需要取一个 (T_i=t_{i,max}=lfloorfrac{c_i-d_i}{x_i}floor+1),同时要满足 (T_igelceilfrac{d_i}mceil)

这样转化以后我们会得到一组 ((d_i,T_i)) 的值。分析一组取值合法的条件,我们按照 (T) 从大到小排序,假设排序后变成 ((d_{p_1},T_{p_1}),(d_{p_2},T_{p_2}),cdots),按照这样的顺序依次选,直接描述就是 必须任意时刻下都能合法地选够 (m) 份疏巨,使用数学语言描述就是

[forall i>0,sum_{k=1}^{i-1}d_{p_k}ge m(p-T_{p_i})
]

(大白话就是前面的所有 (d) 够塞满后 (p-T) 天的销量)

下面考虑多销售一份疏巨时会发生什么变化。某一种疏巨的 (d) 会增加,(T) 可能会减小,如果没减小,式子仍然成立,无事发生;如果减小,只会影响其中的一个不等式(右端 (+m)),但也有可能使得排名发生改变,总结下来就是某一项右边 (+m),某个前缀的所有不等式组,左边项 (+1)。但不可能一个不等式 (+m),一个不等式 (+1)

维护这样的东西即可,每次选择能贪到的最大权来贪一贪就行了。证明感性理解?(反正可以建费用流模型,贪心不会错,好吧其实我不会证)。

仔细思考使用堆维护,复杂度 (mathcal O(max p_i imes mlog n))。注意要先做 (p) 最大的情况,然后再退回来做(每次把不好的疏巨丢了),要不然 (p) 增加的时候不等式不满足条件了。

Code

(咕咕咕)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注