遇到一个钱庄问题，求解答。
钱庄每天能够收到很多散钱，第i个散钱的值 2^wi。为了便于管理，钱庄每天都会向中央银行申请兑换钱币，假设钱庄有一些散钱使得 2^k1+2^k2+...+2^km=2^x（x为非负整数），那么就可以将这些散钱兑换成一个大钱币，问在钱庄收到的这些散钱最终最少能变成几个钱币？输入一个整数 n，表示一共有 n 个钱币 (1<=n<=10^6)；再输入n个整数 wi,表示有价值 2^wi(0<=wi<=10^6)的钱币。输出兑换后最少的钱币数。
展开
收起
1
条回答
写回答
写回答
-
遍历一遍m找出m中的最大数max定义一个数组arr[max+2],用于统计出m数组中，每个数字出现的次数，即arr[m[i]]++（m中的元素为下标，arr 数组中保存出现的数）;再次遍历 arr 数组 (0<=i<=max)，如果当前元素 arr[i]==0，那就下一个，如果不为 0，arr[i+1]+=arr[i]/2;( 每两个 arr[i] 就能凑一个 arr[i+1])如果 arr[i] 为奇数，那说明剩余一个 arr[i]，这最后也就剩下了，所以 ans++；遍历完后 if(arr[max+1]!=0)ans++; 然后 returnans; 则输入：4 [1,1,2,3] 输出：1
2021-12-23 18:25:57赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
