CF730J Bottles思维+01背包
题目
给出n个瓶子,每个瓶子中有一定量的液体。现在可以把一瓶瓶子中的液体倒到其他瓶子中。在保证最后使用瓶子最少的前提下,倒的液体体积最小。
解题思路
最后使用的最小瓶子数很容易,排序贪心一遍即可求出。
现在确定了只能使用$k$个瓶子,且$k$个瓶子的总体积要能装下所有液体。又有,我们选择$k$个瓶子作为最后的容器,那么其他液体都要倒进这几个瓶子中,花费就是$总的液体体积S-这几个瓶子中的液体体积S_2$,$S$为定值,所以$S_2$越大,花费越小。
至此,问题转化成了,$k$个瓶子,求最大价值,且要满足$k$个瓶子的体积大于等于$S$。
前面是典型的01背包问题,后面的条件加上一维即可。
代码
1 |
|