贪心,二进制
很容易想到:把 \(n\) 转化为二进制,考虑如何得到每一位。
很显然,用小的数去“凑出”大的数不花费代价,用大的数“分解”出小的数要花费代价。所以。一个简单的贪心是:设当前要得到 \(n\) 的第 \(i\) 位的数 \(2^i\),尽量用小的数凑,若小的数凑不出,再用大的数分出 \(2^i\)。
如何证明呢?在一些情况下,若当前要凑出的是 \(2^i\),如果按照贪心的思路,用小的来凑,可能有些小的数会被浪费,比如 \(3\) 个 \(2^{i-1}\) 只能凑出 \(1\) 个 \(2^i\),有一个 \(2^{i-1}\) 就被浪费了。所以需要证明的是:后面(从小到大遍历 \(i\))一定不需要用这个多余的 \(2^{i-1}\)。想一想,如果后面我要用这个数,必定还需要一个 \(2^{i-1}\) 合并成 \(2^i\) 后继续合并,来凑出更大的 \(2\) 的幂次(因为从小到大遍历 \(i\),所以后面要凑出的数一定比 \(2^i\) 大)。这个 \(2^{i-1}\) 又怎么来呢?又只有用一个大的数划分到 \(2^{i-1}\),但是请注意,这个大的数划分到 \(2^{i-1}\) 时,实际上会划分出两个 \(2^{i-1}\) ,也就是现在又有 \(3\) 个 \(2^{i-1}\),又有一个会被浪费。那我还用之前剩下的 \(2^{i-1}\) 干嘛?我不如直接用后面的两个 \(2^{i-1}\) 。所以,不管有没有浪费小的,我们都用小的去凑,如果凑不出来,就用后面存在的,最小的数去划分出 \(2^i\)。
\(Code:\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int m;
const int MAXN=1e5+5;
ll a[MAXN];
ll read(){
ll x=0;char c=getchar();bool f=0;
while(c>'9'||c<'0'){f|=(c=='-');c=getchar();}
while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return f?-x:x;
}
int cnt[105];
int main(){
n=read(),m=(int)read();
ll sum=0;
for(int i=1;i<=m;i++){
ll x=read();int t=0;
sum+=x;
while(x){
if(x&1) break;
x>>=1;t++;
}
cnt[t]++;
}
if(sum<n){
printf("-1");
return 0;
}
int ans=0;
for(int i=0;i<=63;i++){
ll now=1ll;now<<=i;
if(i>0) cnt[i]+=cnt[i-1]/2;
if(!(n&now)) continue;
if(cnt[i]) cnt[i]--;
else{
for(int j=i+1;j<=63;j++){
if(cnt[j]){
for(int k=i+1;k<j;k++) cnt[k]++;
ans+=j-i;
cnt[j]--;
break;
}
}
}
}
printf("%d",ans);
return 0;
}