[BZOJ2257] [JSOI2009] 瓶子和燃料

题目

题目链接
大意是你有 n 个瓶子,每个瓶子容量为 v_i 且没有刻度。现在要选出 k 个瓶子给外星人,外星人会将瓶子里的水任意倒,或者倒满一个瓶子,或者倒空一个瓶子。外星人会使剩下的水最少,求出所有给瓶子的方案中外星人最多会剩多少水。
 

思路

首先得明白,任意给 k 个瓶子,外星人最后剩下的水为这 k 个瓶子的最大公约数(参见上篇博文)那么如何选择使得选出来的 k 个数的最大公因数最大呢?如果从选那些数入手的话复杂度很高。所以我们可以从约数入手,去考虑哪些约数是合法的。我们只需记录下所有数的约数,然后看哪个约数出现超过 k 次,找出最大的即可。时间复杂度为 O(n \sqrt{v}).
 

代码

 

完结

参考黄学长博客

发表评论

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