这篇博客我要单独写!
思想:贪心的把到当前位置先补齐
假设:i,j,k,p是位置
i j k p
少 多 少 多
------------------------------------------------------------
i位置缺少
第0步:
花费x
------------------------------------------------------------
j位置是多出来,如果转移更优,则满足
(j - i) * z < x(把i位置及填满需要这么多钱) + y(把j位置多的去掉需要这么多)
“把j位置多的去掉的更少花费”
v = (j-i)*z - x
观察
v = (j-i) * z - x
= j*z - (x + i*z) //括号里的和什么相关:
//1.i位置填满需要的花费,2.i位置(i*z)
v累加进答案中
这里先不说完整的做法,继续推理,从下面的推导过程让“最终的方法”付出水面
------------------------------------------------------------
k位置是缺少的,如果转移更优,则满足
(k - j) * z < v(把j位置多的去掉的更少花费) + x(把k位置填满)
//把k位置填满的更少花费
w = (k - j) * z - v
= k*z - (v + j*z)//括号里的和什么相关:1.j位置去掉需要的花费,2.j位置有关(j*z)
找到规律:选择前面“多余”的位置中最大的 "花费 + 位置*z",进行交换
累加进答案中,并且 k*z + w 放入“缺少”大根堆
如果转移不优,则
(k - j) * z > v(把j位置多的去掉的更少花费) + x(把k位置填满)
则把x累加到答案中
k*z + x 放入大根堆
------------------------------------------------------------
p位置是多出来的,如果转移更优,则满足
(p - k) * z < w(把k位置填满的更少花费) + y(p位置去掉)
r = (p - k) * z - w
= p * z - (k*z + w) //括号里的和什么相关:1.k位置填满需要的花费,2.k位置有关(k*z)
找到规律:选择前面“缺少”的位置中最大的"花费 + 位置*z",进行交换
累加进答案中,并且 p*z + r 放入"多余"大根堆
标签:P3049,填满,花费,位置,更少,------------------------------------------------------------,L From: https://www.cnblogs.com/caterpillor/p/16945235.html