在 byteotian 公司搬家的时候, 他们发现他们的大量的精密砝码的搬运是一件恼人的工作. 公司有一些固定容量的容器可以装这些砝码. 他们想装尽量多的砝码以便搬运, 并且丢弃剩下的砝码. 每个容器可以装的砝码数量有限制, 但是他们能够装的总重量不能超过每个容器的限制. 一个容器也可以不装任何东西. 任何两个砝码都有一个特征, 他们的中总有一个的重量是另外一个的整数倍, 当然他们也可能相等.
Solution
关键的地方就是任意两个物品之间都是整数倍之间的关系.
我们可以吧每个容器 k 进制拆分, 那么我们把物品从小到大依次加入, 如果当前位不满足, 就从高位借.
- Code
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- #define N 100002
- using namespace std;
- int a[N],b[N],c[N],tot,d[N],ji[N],n,m;
- int dfs(int id){
- if(id>tot)return 0;
- if(d[id])return d[id]--,1;
- if(dfs(id+1)){
- d[id]+=c[id+1]/c[id],d[id]--;
- return 1;
- }
- return 0;
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i)scanf("%d",&a[i]);
- for(int i=1;i<=m;++i)scanf("%d",&b[i]);
- sort(b+1,b+m+1);
- for(int i=1;i<=m;++i){
- if(b[i]!=b[i-1])c[++tot]=b[i];
- ji[i]=tot;
- }
- for(int i=1;i<=n;++i)
- for(int j=tot;j>=1;--j){
- d[j]+=a[i]/c[j];a[i]%=c[j];
- }
- int now=1;
- for(int i=1;i<=m;++i){
- if(!dfs(ji[i])){
- printf("%d",i-1);
- return 0;
- }
- if(i==m)cout<<m;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2825322.html