CodeForces - 1303D Fill The Bag(贪心+模拟)

题目链接：点击查看

题目大意：给出一个背包，容量为 k ，再给出 n 个物品，每个物品的大小保证是 2 的幂次，现在可以进行操作，使得一个物品分为大小相等的，且大小等于原物品一半的两个物品，比如一个物品原来为 4 ，可以分为两个 2 ，现在问最少需要操作多少次，才能让物品恰好装满背包

题目分析：因为题目提示的很明显了，给出的物品以及操作都是对于 2 的幂次进行操作，所以可以将背包容量 k 进行二进制分解，然后从最低位开始贪心填满即可，如果当前位置有物品的话，直接用这个物品填满，如果没有物品的话，就必须要找到首个大于当前位置的物品进行拆分，知道这个贪心策略后剩下的就是模拟了

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int a[N],cnt[100];int get_num(int num)//返回当前的数字为2的多少次幂 {int ans=0;while(num){ans++;num>>=1;}return ans-1; } int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); //#endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){memset(cnt,0,sizeof(cnt));LL n,m;scanf("%lld%lld",&n,&m);LL sum=0;for(int i=1;i<=m;i++){scanf("%d",a+i);cnt[get_num(a[i])]++;//统计每个物品，转换成2的幂次sum+=a[i];}if(sum<n)//特判-1{printf("-1\n");continue;}vector<int>bit;while(n)//将背包容量转换为二进制{bit.push_back(n%2);n>>=1;}int ans=0;for(int i=0;i<bit.size();i++)//从最低位开始贪心{if(bit[i])//如果此位需要物品装填{int pos=i;if(!cnt[pos])//如果当前位置没有物品，则向上寻找{while(!cnt[pos]){cnt[pos]++;pos++;ans++;}cnt[pos]--;//被分解的物品需要减一cnt[i]++;//最低位需要加一}cnt[i]--;//直接使用物品填补背包}cnt[i+1]+=cnt[i]/2;//用较低的位更新较高的位}printf("%d\n",ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1303D Fill The Bag(贪心+模拟)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。