首页 > 代码库 > Codeforces 309C Memory for Arrays 二进制模拟进位
Codeforces 309C Memory for Arrays 二进制模拟进位
题目链接:点击打开链接
题意:
给定n个箱子m个物品
下面n个数字表示箱子的容量
下面m个数字b1-bm 表示物品体积为2^bi大
问最多有多少个物品可以放入箱子。
思路:
贪心,先放小的,小的不能放再放大的
显然我们把n个箱子拆成二进制,然后模拟二进制减法运算。
剩下就是简单模拟
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> #include<set> #include<queue> #include<map> #include<vector> using namespace std; #define ll __int64 #define N 50 ll n,_gcd,m,k; ll a[N],b[N],er[N]; bool jie(ll pos, ll ge){ bool hav = false; ll now; for(ll i = pos+1; i < N; i++) if(a[i]){ hav = true; now = i; break; } if(hav==false)return false; ll ned = ge / er[now-pos]; if(ned==0){ a[now]--; a[pos]++; for(ll i = pos; i < now; i++) a[i]++; return true; } ned = min(ned, a[now]); a[now] -= ned; a[pos] += ned*er[now-pos]; return true; } int main(){ ll i, u; for(i=0, u = 1;i<N;i++, u<<=1) er[i] = u; while(cin>>n>>m) { memset(a, 0, sizeof a); memset(b, 0, sizeof b); while(n--){ scanf("%I64d",&u); for(i=0;i<N && u>=er[i];i++){ if(u&er[i]){ a[i]++; } } } ll ans = 0; while(m--){ scanf("%I64d",&u); b[u]++; } bool hav = false; for(i=0;i<N;i++)if(b[i]){ while(b[i]){ ll now = min(a[i],b[i]); ans += now; a[i]-=now; b[i]-=now; if(b[i]) { if(!jie(i, b[i])) { hav = false; break; } } else break; } if(hav)break; } cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。