Coins and Queries（map迭代器+贪心）

题意

n个硬币，q次询问。第二行给你n个硬币的面值（保证都是2的次幂！）。每次询问组成b块钱，最少需要多少个硬币？

Example Input 5 4
2 4 8 2 4
8
5
14
10 Output 1
-1
3
2

解题思路：总体上使用的是贪心策略，从最大面值的往下贪心选择就可以了，由于数据量较大这里使用了map,这样就最多才32个数。第一次使用map的迭代器

反向迭代器的rbegin和rend的位置
和正向迭代器的begin和end的位置如下图

  1 #include<cstdio> 2 #include<map> 3 #include<algorithm> 4 using namespace std; 5 map<int,int>mp;///这里键存储的是硬币的面值，值存储的是硬币的个数 6 int main() 7 { 8 int n,m,i; 9 scanf("%d%d",&n,&m); 10 for(i=0; i<n; i++) 11 { 12 int x; 13 scanf("%d",&x); 14 mp[x]++; 15 } 16 while(m--) 17 { 18 int ans=0; 19 int flag=0; 20 int a,t; 21 scanf("%d",&a); 22 map<int,int>::reverse_iterator it;///反向迭代器 23 for(it=mp.rbegin(); it!=mp.rend(); it++) 24 { 25 t=min(a/it->first,it->second); 26 ans+=t;///t只有是整数的时候才会用来计数 27 a=a-t*it->first; 28 if(!a)///当a=0是恰好完全取完 29 { 30 flag=1; 31 break; 32 } 33 } 34 if(flag==1) 35 { 36 printf("%d\n",ans); 37 } 38 else 39 { 40 printf("-1\n"); 41 } 42 } 43 return 0; 44 }

 

 

转载于:https://www.cnblogs.com/wkfvawl/p/9378687.html

总结

以上是生活随笔为你收集整理的Coins and Queries（map迭代器+贪心）的全部内容，希望文章能够帮你解决所遇到的问题。

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