二进制处理N，拆分成若干个2的i次方，然后记录下每个2的次方有多少个盒子，按位查询N拥有的2的次方盒子有没有，没有的话就往上找大的盒子拆，如果盒子没用上就合并成大的盒子。
#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<cmath> #include<cstdio> using namespace std; typedef long long ll; ll sum[65],a[65]; ll t,n,m,ans; int main() { cin>>t; sum[0]=1; for(int i=1;i<=60;i++) sum[i]=sum[i-1]*2; while(t--) { cin>>n>>m; ans=0; ll num=0; memset(a,0,sizeof(a)); for(int i=0;i<m;i++) { ll x; cin>>x; num+=x; for(int j=0;j<=60;j++) if(sum[j]==x) { a[j]++; break; } } if(num<n) { cout<<-1<<endl; continue; } for(int i=0;i<=60;i++) { if(n&((ll)1<<i))//二进制判断这一位是不是1 { if(a[i]!=0) a[i]--; else { int k=i; while(!a[k])//往上找可以分成两份的一项 { a[k]++; k++; ans++; } a[k]--; } } a[i+1]+=a[i]/2;//合并没有用到的低位项 } cout<<ans<<endl; } }