蒟蒻的小窝

蒟蒻的小窝

题解 P3462 【[POI2007]ODW-Weights】

posted on 2020-11-28 10:05:41 | under 题解 |

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