遇到一个需要找出最大值问题，求解答。
Tom 非常喜欢巧克力，他上次买的巧克力吃完了，所以他打算再去买 k 块巧克力回来 (1<=k<=1e5)，他又是一个非常节俭的一个人，所以他想花最少的钱去买巧克力。现在有 n 家卖巧克力的店 (1<=n<=1e5)，每个店的巧克力都限购 bi 块 ( 最多只能买 bi 块 ,1<=bi<=1e5)，每块的价格是 ai(1<=ai<=1e9)，请问 Tom 买 k 块巧克力最少要花多少钱？题目保证 n 个 bi 的总和大于等于 k。输 入 卖 巧 克 力 的 店 的 个 数 n(1<=n<=1e5)； 打 算 去 买 的 巧 克 力 块 数k(1<=k<=1e5)；和一个数组 m, 其中 mi=ai,bi 表示第 i 家巧克力店的巧克力的价格和限购块数输出一个数，表示 Tom 买 k 块巧克力花的最少钱数。
写回答
-
根据题意，可以得知这道题可以运用贪心算法，策略是每次都去买最便宜的巧克力。由于题目给的二维数组是乱序的，可以根据巧克力的价格对二维数组从小到大进行排序，便于Tom选择最便宜的巧克力。Arrays 类中只提供了一维数组的排序，如果要用 Arrays对二维数组排序，需要重写 Comparator 里的 compare 方法。排序完成后，接下来操作就比较简单了。遍历数组，优先买便宜的巧克力，直到达到限购块数，再去下一家巧克力店。最终买到k块巧克力时 Tom 花的钱最少。 因此输入：2 5 [[4,5],[2,4]] 输出： 12
2021-12-23 18:17:11赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
