算法筆試模拟題精解之“Tom愛吃巧克力”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

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)

看完之後是不是有了想法了呢，快來練練手吧>>