题解 P3462 【[POI2007]ODW-Weights】

· · 题解

砝码两两互为倍数关系，从小到大排个序，可以发现不同的砝码种类数是 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;
}