自动搬运

查看原文

来自洛谷，原作者为

	VioletIsMyLove AFO

搬运于2025-08-24 21:49:14，当前版本为作者最后更新于2020-11-28 10:05:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

砝码两两互为倍数关系，从小到大排个序，可以发现不同的砝码种类数是 $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)$。以此类推。其实就是小学减法嘛，不要搞错，依次借位就ok了。

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,a[maxn],b[maxn],num[maxn],c[35],tot,cnt[35];
int read(){
    int ret=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
    return ret*f;
}
int DFS(int id){//首先核对是否够-，不够要依次借位 
    if (id>tot)return 0; 
    if (cnt[id])return cnt[id]--,1;
    if (DFS(id+1)){
      cnt[id]+=c[id+1]/c[id],cnt[id]--;
      return 1;
    }
    return 0; 
}
int main(){
    n=read(),m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=m;i++) b[i]=read(); 
    sort(b+1,b+m+1); 
    for (int i=1;i<=m;i++){
      if(b[i]!=b[i-1]) c[++tot]=b[i];
      num[i]=tot;
    }
    for (int i=1;i<=n;i++)
    for (int j=tot;j;j--)
      cnt[j]+=a[i]/c[j],a[i]%=c[j];
    for (int i=1;i<=m;i++){
      if(!DFS(num[i])){printf("%d\n",i-1);return 0;}
      if(i==m)printf("%d\n",m);
    }
    return 0;
}