这道题就是有n枚硬币，每个硬币的币值都是2的次方（比如2 4 8 16之类的） 然后有q次询问，每次输入一个数，我们要用最少的硬币达到这个币值，如果存在结果的话就输出这个最小的使用硬币数，如果不存在的话，就输出-1

这道题应该算是一道贪心的题，我们先将2的各次方存到一个数组里，之后询问的时候，就先从最大的2的31次方开始找，然后记录一下就可以啦！

以下是代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,q;
int sum[32];
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
int k;
scanf("%d",&k);
int t=log2(k);
sum[t]++;
}
for(int i=1;i<=q;i++)
{
int k,ans=0;
scanf("%d",&k);
for(int j=31;j>=0;j--)
{
int cur=min(sum[j],k/(1<<j));
ans+=cur;
k-=(1<<j)*cur;
}
if(k!=0) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}

 

版权声明：本文为fengxunling原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/fengxunling/p/9337666.html