[bzoj1110][POI2007]砝码Odw_贪心

时间：2021-07-25 16:50:39

bzoj-1110 POI-2007 砝码Odw

参考博客：http://hzwer.com/4761.html

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

数据范围：$1\le n,m\le 10^5$，$1\le w_i\le 10^9$，$1\le m_i\le 10^9$。

想法：

题目的意思就是把所有砝码从小到大排序之后，后一个是前一个的倍数。

那么对于一个容量来讲，如果是最小的数的倍数，就一定可以被像进制一样被这$n$个数表示出来。

那么我们就从低往高了添就好了。

如果当前位没有了就向上一位借即可。

[bzoj1110][POI2007]砝码Odw_贪心

代码：

#include <bits/stdc++.h>

#define N 100010

using namespace std;

int a[N],b[N],c[N],s[N];

char *p1,*p2,buf[100000];

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int rd() {int x=0,f=1; char c=nc(); while(c<48) {if(c=='-') f=-1; c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}

int main()

{

	int n=rd(),m=rd();

	for(int i=1;i<=n;i++) a[i]=rd();

	for(int i=1;i<=m;i++) b[i]=c[++c[0]]=rd();

	sort(b+1,b+m+1); sort(c+1,c+c[0]+1);

	c[0]=unique(c+1,c+c[0]+1)-c-1;

	// cout << c[0] << endl ;

	for(int i=1;i<=n;i++)

		for(int j=c[0];j;j--)

			s[j] += a[i]/c[j], a[i]%=c[j];

	// for(int i=1;i<=c[0];i++) printf("%d ",s[i]);

	// cout << endl ;

	int ans=0;

	for(int i=1;i<=m;i++)

	{

		// cout << b[i] << endl ;

		int l=lower_bound(c+1,c+c[0]+1,b[i])-c,r=l;

		// cout << l << ' ' << r << endl ;

		while(r<c[0] && !s[r]) r++;

		// cout << r << endl ;

		if(!s[r]) break;

		for(int j=l;j<r;j++) s[j] ++ ;

		s[r] -- ;

		ans ++ ;

	}

	cout << ans << endl ;

	return 0;

}

小结：贪心不难想到，怎么贪心就比较神奇。

　　看见这种序列往进制上想。

相关文章