3139. 讓矩陣每個元素的值都相同的最小花費 (Beats 100%)
=====================
難度: Hard
類型: Array, Greedy, Enumberation
CPP程式下載: 3139_2.cpp
=====================
覺得 minimum cost 類型的題目很生疏, 挑幾題來練習, 結果挑上一個難題。
這次不直接對"vector<int> nums"做操作, 直接用算的。
=====================
前情題要:
cost1 是矩陣內的一個元素值加1, 所需要的花費
cost2 是矩陣內的兩個元素值都加1, 所需要的花費
Input: vector<int> nums , int cost1, int cost2
Output: Minimum cost
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1061 <= cost1 <= 1061 <= cost2 <= 106
=====================
思考方式:
1. 算出最小值, 最大值, 還有"vector<int> nums"所有數字加總。
2. 如果 cost1 * 2 <= cost2, 那直接每個數字都直接加一操作, 就可得到最小花費。
3. 考量例外情況, 如果nums_size 是1, 回傳 0, 如果num_size是2, 只能做 cost1的操作, 結果就如同 step2。
4. 接著就是cost1 * 2 > cost2, 這情形要先做 cost2, 先盡量把所有的數字都變成最大值, 然後剩下的再用 cost1 補齊, 或是繼續做 cost2操作 (max_num也會同時被加一, cost2 操作)。
5. 但步驟4不一定得到最小花費, 可能還能繼續做 cost2 的操作, 所有數字在大於 max_num 的情形下達成一致。
6. 引進 target 值的概念, 就是最後每個數字都被加到變成 target。 target 從 max_num 開始, 逐漸加1。
7. cost2操作就是一次兩個數字都加1, 最大的gap在"target - min_num"上, 如果這個gap值大於 "total gap = (target* nums_size - sum_num)" 的一半, 代表 當其他數字都被加到 target, 原本最小的那個值, 還沒到 target, 就需要用 cost1 操作來補足。
8. 如果最大的gap小於或等於total gap的一半, 代表最後會剛好被cost2操作補滿, 或是剩下一個 cost1的花費。
9. 停止時機, 如果 target + 1 後, 算出來的 minimum cost沒有更低, 就可以結束了。不然後面只會越來越大, 不會再出現更低的 minimum cost了。
註1: Coding 時要注意, int * int 可能會超過最大值, int+int 也可能超過最大值, 此時記得把某一個int 被臨時宣告成 (long), 後面運算的結果才會被當成是 long 然後不會產生 runtime (overflow) error。
註2: 記得在accumulate中輸入最後一個參數是 0L, 這個L很重要, 不然也會產生 runtime error, 而且錯誤的行號並不會指出你程式內的位置。
accumulate(nums.begin(), nums.end(), 0L);
=====================
複雜度思考:
難的是要想到這樣的運算方式。通常要經歷失敗過程數次才能想通。
這樣的運算沒有重疊的迴圈, 最麻煩的只有算出 max, min, sum, 時間上並沒有多餘的浪費。
在記憶體上也沒有另外產生新的 verctor 來暫存, 所以在空間上也是很有效率的。
Time: O (n+x)
Memory: O (x)
=====================
結果:
636 / 636 testcases passed
Runtime: 0 ms, Beats: 100%
Memory: 94.34 MB, Beats: 86.44%
