在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的 第56题：Tom爱吃巧克力 的题目解析，具体如下：

题目描述

题目等级：容易
知识点：贪心

查看题目：Tom爱吃巧克力
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块巧克力花的最少钱数

示例1
输入：
2
5
[[4,5],[2,4]]
输出：
12

解题思路：贪心

根据题意，可以得知这道题可以运用贪心算法，策略是每次都去买最便宜的巧克力。

由于题目给的二维数组是乱序的，可以根据巧克力的价格对二维数组从小到大进行排序，便于 Tom 选择最便宜的巧克力。Arrays 类中只提供了一维数组的排序，如果要用Arrays对二维数组排序，需要重写Comparator里的compare方法。

排序完成后，接下来操作就比较简单了。遍历数组，优先买便宜的巧克力，直到达到限购块数，再去下一家巧克力店。最终买到 k 块巧克力时 Tom 花的钱最少。

时间复杂度：O(n)
空间复杂度：O(1)

看完之后是不是有了想法了呢，快来练练手吧>>查看题目：Tom爱吃巧克力