算法筆試模拟題精解之“打怪獸”

線上程式設計介紹

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

https://developer.aliyun.com/coding

本文為大家介紹其中的 第43 題：打怪獸 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：排序、貪心

檢視題目：打怪獸

現在有3隻怪獸，他們的都有自己的血量a,b,c(1<=a,b,c<=100)，當Tom打死第一怪獸的時候花費的代價為0，其餘的怪獸的代價為目前的怪獸的血量減去上一個怪獸的血量的絕對值。問Tom打死這些怪獸所需要的最小代價?

分别輸入三隻怪獸的血量；

輸出打死三隻怪獸的最小代價。

示例1

輸入：

2

5

8

輸出：

6

解題思路：貪心

貢獻者 | 郭達彬

根據題意，本題使用貪心算法完成，政策是每次打怪獸都選擇代價最小的一隻。

由于第一次打怪獸的花費為0，是以第一次可以打血量最小的（最大的也可以），接下來每次選擇怪獸的時候就可以選擇花費代價最小的。由于每次打怪獸的代價都是：目前怪獸的血量和上一個怪獸的血量的差的絕對值。于是可以得出結論，最小代價為所有怪獸血量的最大值減最小值。

時間複雜度：O(1)

空間複雜度：O(1)

趁熱打鐵，題目直達連結：

43題：打怪獸