【bzoj1110】[POI2007]砝码Odw

2014年10月20日1,9813

Description

在byteotian公司搬家的时候,他们发现他们的大量的精密砝码的搬运是一件恼人的工作。公司有一些固定容量的容器可以装这些砝码。他们想装尽量多的砝码以便搬运,并且丢弃剩下的砝码。每个容器可以装的砝码数量有限制,但是他们能够装的总重量不能超过每个容器的限制。一个容器也可以不装任何东西。任何两个砝码都有一个特征,他们的中总有一个的重量是另外一个的整数倍,当然他们也可能相等。

Input

输入文件的第一行包含两个数n和m。表示容器的数量以及砝码的数量。(1<=n, m<=100000) 第二行包含n个整数wi,表示每个容器能够装的最大质量。(1<=wi<=1000000000) 第三行包含m个整数mj,表示每个砝码的质量。(1<=mj<=1000000000)

Output

输出文件要求仅包含一个数,为能够装进容器的最多的砝码数量。

Sample Input

2 4
13 9
4 12 2 4

Sample Output

3

题解

复制个鏼爷的题解。。。

砝码两两互为倍数关系,从小到大排个序,可以发现不同的砝码种类数是log(10^9)级别的,只有30左右。
根据贪心的思想,砝码从小到大依次装入一定是最优的
把每个容器的容量写成砝码大小的进制表示,比如当有3,9,18,54这些种类的砝码时,133的容量可以写成2*54+1*18+0*9+2*3+1,末尾的+1永远用不上,可以舍弃,那么各位从低到高分别是(2,0,1,2)。
把所有容器都写成这种表示,并把同一位上全部累加。比如说我们还有一个容器(0,1,2,0),那么两个容器累加的结果就是(2,1,3,2)。
当我们正在放大小为3的砝码时,就使用最低位上的容量。比如我们只有1个大小为3的砝码,那么塞入以后剩余容量为(1,1,3,2)。接下来要放大小为9的砝码,最低位上的那个1就永远用不上了。假如我们有2个9,而第二位上只有1的容量,那么就往高位借一个18拆成两个9,变成(2,3,2,2),然后塞入后剩余(2,1,2,2)。以此类推。
当剩余容量不够再放入时即停止,当前已放入的砝码个数即为最优答案。

 

 

  • lt*2015年9月14日 下午8:11 回复

    我是lt*,我爱您!

    #1  
  • 陆葳蕤pastos2015年9月17日 下午8:24 回复

    好朴素的做法……好有效的做法……

    #2  
  • jcvb2016年11月5日 上午10:26 回复

    orz 金策爷

    #3