AT_abc144_e [ABC144E] Gluttony 题解

· · 题解

题目大意：

有两个数组 a_i 和 f_i 我们可以任意选取若干个 a_i 使他们共减少 k 问怎样减少才能使 {\textstyle \sum_{i=1}^{n}a_i\times f_i} 最小。

分析

我们可以用二分与贪心，是很简单的。首先我们可以想到用人小的去吃数值较大的食品，那么我们就可以把两组数据分别按照从小到大与从大到小进行排序，然后二分找合适的用时，用贪心的方式看看这个时间能否全部吃完，如果能就向下再二分，否则向上。这样就没有问题了。

代码不贴，按照上述思路操作即可。

鸣谢

感谢@do_it_tomorrow 代价应该是乘积的最大值而而非乘积之和。