在線編程介紹
阿里雲開發者社區在線編程產品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費在線刷題神器。題庫來自筆試模擬題、算法大賽模擬題等，界面整潔明瞭，操作簡單，為用戶營造專心答題的學習環境。點擊鏈接開始體驗：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愛吃巧克力