3139. Minimum Cost to Equalize Array, part 1

 3139. 讓矩陣每個元素的值都相同的最小花費 (Time Limit Exceeded) 

=====================

3139. Minimum Cost to Equalize Array

難度: Hard

類型: Array, Greedy, Enumberation

CPP程式下載: 3139_1.cpp

=====================

覺得 minimum cost 類型的題目很生疏, 挑幾題來練習, 結果挑上一個難題。

一樣先從直覺的方法開始, 從過程中學習, 才會誕生更棒的解法。

=====================

前情題要:

cost1 是矩陣內的一個元素值加1, 所需要的花費

cost2 是矩陣內的兩個元素值都加1, 所需要的花費

Input: vector<int> nums , int cost1, int cost2

Output: Minimum cost

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106
• 1 <= cost1 <= 106
• 1 <= cost2 <= 106

=====================

思考方式:

1. 首先判斷 cost1 和 cost2 哪個花費比較划算。兩次 cost1 其實相同於一個 cost2 的動作。

所以如果 cost1*2 <= cost2, 就全部用 cost1 動作, 直到所有元素值相同即可。

2. 有排序似乎比較方便, 因為能知道矩陣內的最大值, 也能從最小值, 以及次大值開始算。(次大值就是從小到大找到的第一個最大值的 index 再減一)

3. 如果不幸的 cost2 < cost1*2, 就要把最小值和次大值都加一, 然後尋找目前陣列的 minumum cost。

=====================

結果:

599/636 test cases passed

第600個 test case下出現了 Runtime 超時的結果。

觀察一下這個出問題的 test case

nums 共有 10^5 個數, 除了第一個數是10^5之外, 其他都是 1

到這邊應該打住了, 因為不可能真的去操作矩陣做 cost1 與 cost2 的動作, 太費時。

正解應該有特別的算法。