主題
題目連結：
題目意譯：
你被給定兩個索引值從 0 開始的陣列 nums 和 cost，其各自由 n 個正整數組成。
你可以執行以下操作任意次數：
將陣列 nums 中任一元素之值增加或減少 1。
而在第 i 個元素執行一次操作的成本為 cost[i]。
回傳最少所需之成本使得陣列 nums 之所有元素之值相等。
限制：
n == nums.length == cost.length
1 ≦ n ≦ 10 ^ 5
1 ≦ nums[i], cost[i] ≦ 10 ^ 6
測資之生成滿足輸出之值不會超過 2 ^ 53 - 1。
範例測資：
範例 1：
輸入： nums = [1,3,5,2], cost = [2,3,1,14]
輸出： 8
解釋： 我們可以用以下步驟使得所有元素變成 2：
- 將第 0 個元素增加一次。成本為 2。
- 將第 1 個元素減少一次。成本為 3。
- 將第 2 個元素減少三次。成本為 1 + 1 + 1 = 3。
總成本為 2 + 3 + 3 = 8。
可以證明沒辦法用更少的成本來讓陣列中所有元素相等。
範例 2：
輸入： nums = [2,2,2,2,2], cost = [4,2,8,1,3]
輸出： 0
解釋： 所有元素已經相等，所以不需要額外操作。
解題思維：
定義一個函數 F(x) = |nums[0] - x| × cost[0] + |nums[1] - x| × cost[1] + …… + |nums[n - 1] - x| × cost[n - 1]，代表著我們把 nums 中所有數字都變成 x 所需的最小成本（即不做加加減減的多餘操作）。
可以看到該函數會在數線上從負無窮大看向正無窮大會得到 F(x) 之值先遞減再遞增之現象，代表著此函數為一個凸函數（Convex Function）。
而對於凸函數，我們便可以採取對「答案」（這邊指的是 x 之值，也就是說要讓 nums 中的數字統一變成何數）本身進行二分搜尋法（Binary Search）的策略，如這題。
我們一次猜兩個數字 M 和 M + 1，並觀察兩者的函數值 F(M) 和 F(M + 1)。如果 F(M) > F(M + 1)，則表示我們在最小值的「左側」，因此我們可以將 M 值猜大一點；如果 F(M) < F(M + 1)，則表示我們在最小值的「右側」，因此我們可以將 M 值猜小一點；而如果 F(M) = F(M + 1)，則代表 M 和 M + 1 都是我們要找的（可以得到最小值的 x 值可能很多個，類似於這題）。剩下的部分跟一般在對答案進行二分搜的方式一致。
最後得到想要的 x 值後，再掃過一次（或是利用過程中計算出來的成本值）得到 F(x) 之值即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
