设所有砝码质量离散去重后为b1,b2,……,bk，那么将每一个容器都表示为$wi-C=\sum_{i=1}^{k}bi\cdot si$（其中$C<b1$且对于$1\le i<k$，有$bi\cdot si<b_{i+1}$），把他看成一个进制，直接作减法即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 int n,m,k,ans,a[N],w[N],s1[N],s2[N]; 5 long long b[N]; 6 int main(){ 7 scanf("%d%d",&n,&m); 8 for(int i=1;i<=n;i++)scanf("%d",&w[i]); 9 for(int i=1;i<=m;i++)scanf("%d",&a[i]); 10 sort(a+1,a+m+1); 11 for(int i=1;i<=m;i++) 12 if ((i==1)||(a[i]!=a[i-1])){ 13 b[++k]=a[i]; 14 s2[k]=1; 15 } 16 else s2[k]++; 17 for(int i=1;i<=n;i++) 18 for(int j=k;j;j--){ 19 s1[j]+=w[i]/b[j]; 20 w[i]%=b[j]; 21 } 22 ans=m; 23 for(int i=1;i<=k;i++){ 24 int las=-1; 25 for(int j=i;j<=k;j++) 26 if (s2[i]*b[i]<=s1[j]*b[j]){ 27 las=j; 28 break; 29 } 30 else s2[i]-=s1[j]*b[j]/b[i]; 31 if (las>=0){ 32 long long s=(s2[i]*b[i]+b[las]-1)/b[las]; 33 s1[las]-=s; 34 s=s*b[las]-s2[i]*b[i]; 35 for(int j=las-1;j>=i;j--){ 36 s1[j]=s/b[j]; 37 s%=b[j]; 38 } 39 s2[i]=0; 40 } 41 ans-=s2[i]; 42 } 43 printf("%d",ans); 44 }