CF1303D Fill The Bag（位运算）

CF1303D Fill The Bag

题意：给你两个数字 n,m

然后下面跟着 m个 2的任意次方 的数 让你用这m个数中的 某些之和组成 数字n 可以对 这些数的某一个 进行分解 比如 2^5=32进行一次分解 16 + 16 输出 最小的分解次数，如果没有合适答案 输出-1

问题分析：位运算+贪心

看到 2进制 显然想到的 就是位运算 因为 存在 最小问题，一般就是 贪心之类（当然有时CF故意让你往难的想） 如果是最小问题：就必须把 原本存在的 的2某次方全部减去，这样才能保证最少 显然，for循环 从 2^0到 2^63是无法实现的，因为 你只能 顺讯或者倒叙 统计大小 便于判断不存在的情况 顺序 扫 可能存在 减去大数刚好合适，，减去小数大数就需要分解 倒叙。。。倒是可以处理第一遍，然后从小的往上扫一遍找到第一个大于的 分解 然后 统计数组-- 次级+2然后 再重复操作倒叙 直到。。。。n==0

通过位运算 可以 清楚地知道n二进制每一位 并直接对每位 的直接操作 从最低位 往高位，低位不足 高位补位，低位 冗余 ，高位进位（>>1）

AC代码：

#include<iostream> #include<cstdio> #include<cstring> #include<bitset> #include<sstream> #include<string.h> #include<iomanip> #include<cmath> #include<algorithm> #include<cstdlib> #include<set> #include<map> #include<queue> #include<vector> using namespace std; #define ll long long #define lowbit(x) (x)&(-x) #define mem(a,b) memset((a),(b),sizeof(a)); const ll inf=0x3f3f3f3f;//1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a)); typedef pair<int ,int > PII; const int nn=1e6+10; ll cnt[64]; int main() { //#define io #ifdef io freopen("in.txt","r",stdin); #endif int t; cin>>t; while(t--){ mem(cnt,0); ll sum=0,n,m; cin>>n>>m; for(int i=0;i<m;i++){ int x; cin>>x; sum+=x; int p=0; while((x>>p)>1)p++;//统计 各位 cnt[p]++; } if(sum<n){ cout<<-1<<endl; continue; } int idx=0,ans=0; while(n||cnt[idx]<0){ cnt[idx]-=(n&1);//n的最后一位 if(cnt[idx]<0){//低位不足 cnt[idx+1]--;//高位补位 ans++; }else{ cnt[idx+1]+=(cnt[idx]>>1);//低位冗余，向高位进位 } n>>=1;//最后一位操作完，左移一位 idx++; } cout<<ans<<"\n"; } return 0; }