题意

有m个砝码，每个砝码有一定的重量w，且满足若w[i]<=w[j]则w[j]必为w[i]的倍数。现在有n个容器，每个容器都有一定的容量，问最多可以放多少个砝码进容器里面。 n,m<=100000

分析

背包……显然不可做。那么就考虑贪心咯。我一开始的想法是二分答案，然后每次把最大的砝码放进剩余容量最大的容器里面，然后用一个优先队列来维护，但复杂度是 O(nlog2) ，信仰不够所以没去打，于是便去看了题解。

考虑到有倍数关系这个条件，所以可以运用进制的思想，比如当有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)。以此类推。 当剩余容量不够再放入时即停止，当前已放入的砝码个数即为最优答案。 （以上是鏼爷的题解）

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define N 100005 using namespace std; int n,m,w[N],v[N],s[N],a[N]; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&w[i]); for (int i=1;i<=m;i++) { scanf("%d",&v[i]); a[i]=v[i]; } sort(a+1,a+m+1); sort(v+1,v+m+1); int m1=unique(a+1,a+m+1)-a-1; for (int i=1;i<=n;i++) for (int j=m1;j>=1;j--) { s[j]+=w[i]/a[j]; w[i]%=a[j]; } int ans=0; for (int i=1;i<=m;i++) { int x=lower_bound(a+1,a+m1+1,v[i])-a,y=x; while (!s[y]&&y<=m1) y++; if (y>m1) break; s[y]--; for (int j=x;j<y;j++) s[j]++; ans++; } printf("%d",ans); return 0; }