【BZOJ1110】[POI2007]砝码Odw

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

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

　　仅包含一个数，为能够装进容器的最多的砝码数量。

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int n,m,len,ans;int bas[50],w[100010],v[100010],c[50];int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int main(){	n=rd(),m=rd();	int i,j;	for(i=1;i<=n;i++)	w[i]=rd();	for(i=1;i<=m;i++)	v[i]=rd();	sort(v+1,v+m+1);	for(i=1;i<=m;i++)	{		if(v[i]>bas[len])	bas[++len]=v[i];		v[i]=len;	}	for(i=1;i<=n;i++)	for(j=len;j;j--)	c[j]+=w[i]/bas[j],w[i]%=bas[j];	for(i=1;i<=m;i++)	{		if(c[v[i]])	c[v[i]]--,ans++;		else		{			for(j=v[i];j<=len;j++)			{				if(c[j])				{					c[j]--;					break;				}				c[j]=bas[j+1]/bas[j]-1;			}			if(j>len)	break;			else	ans++;		}	}	printf("%d",ans);	return 0;}