筆試算法模拟題精解之“數組變換”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“數組變換”的解法探究。先來看一下題目内容：

題目詳情

等級：中等

知識點：排序、貪心

檢視題目：數組變換

給出一個長度為 n 的數組，和一個正整數 d。你每次可以選擇其中任意一個元素 a[i] 将其變為 a[i] + d 或 a[i] - d，這算作一次操作。

你需要将所有的元素全部變成相等元素，如果有解，請輸出最小操作次數，如果無解請輸出-1。

輸入數字n、數字d，和一個長度為n的數組a。1 <= n <= 100000，1 <= d <= 100, 1 <= a[i] <= 100000。

輸出一個數字，表示最小的操作次數，如果無解輸出-1。

示例1

輸入：

5

2

[3,5,7,1,9]

輸出：

6

注意

最優解為全部變為5，共1 + 0 + 1 + 2 + 2 = 6次。

解題方法：

貢獻者 | 猿圈

首先判斷無解的情況，可以發現 a[i]，a[i]+d, a[i]-d 在 模d情況下的餘數不會發生改變，是以如果原數組中的存在任意兩個數字它們對d取餘結果不同，那麼此時無解。

設餘數為r。判斷完無解之後，需要求出最小值。

先将數組a[i]排序，然後除以d，得到從r變成a[i]需要的步數。

枚舉元素a[i]，将所有元素全部變成a[i]需要考慮兩部分，i之前和i之後:對于i之前的元素，假設都是r，那麼需要 (i-1)

*

a[i]，但是因為并不都是0，所有我們可以用一個變量val存放前i-1項的和，然後我們在減去val就是前i-1個元素真正需要操作的步數。

對于i之後的元素，也是類似的。我們假設i之後的所有項和為val，假設我們要将它們變為r，則消耗即為val，但是我們隻需要将其變為a[i]，是以需要減去(n-i)*a[i]。

看完之後是不是有了答題思路了呢，快來練練手吧：

110.數組變換