最小變速所以它們的差是> = K

Question

我被要求執行一個算法，作爲輸入以下內容：

-A排序整數數組一個，例如A = [0， 0,0,0,0,2,4,4,4,4,4。如果它有助於將實際輸入作爲兩個數組給出，第一個給出整數，第二個給出第一個整數。對於我們的例子[0,2,4]，[5,1,5]。

- 整數k。

並返回一個數組b唯一的實數（兩個小數位），其連續元素不同的至少k和最大差值的| A [1] -b [I] |是最低的可能。數組a和b都是排序的。

到目前爲止，我已經在一轉身兩個給定的陣列，正如我前面所描述的，並經過多次循環管理，使陣列，具有按照以下步驟獨特元素的有序陣列：

- 對於每個多整數的出現，例如5次0，我將它們移到最小可能距離：假設k = 2，然後[0,0,0,0,0] - > [ - 4，-2,0,2,4]。

- 然後我對數組進行排序，以查找由移位引起的多次出現。

- 重複這兩個步驟，直到數組只有唯一的元素。 如果我有辦法將最後一個數組的元素移動到它們所需的位置（所以它們的最終差異> = k），我假設後面到起始數組的差異將由我請求的移位決定。

我的整個想法可能是錯誤的或過慢，但我已經達到了這個問題一個死衚衕，所以任何幫助將是巨大的！先謝謝你 ！！！

P.S.我列舉了一個小例子，使整個事情變得更加清晰： K = 2，a = [0,1]，b = [3,1]（ - > c = [0,0,0,1] ），所以我們的結果應該是[-2,5，-0,5，1,5，2,5]，這使最大最小偏移2.50。

Answer 1

如果max-min <= k*n，那麼陣列b是

M+0, M+k, M+2k, ..., M+(n-1)k 

其中M滿足

|max-M-k(n-1)| = |min-M|. 

所有你需要 關心的是 陣列a的第一個和最後一個元素，只要您的連續陣列b元素 相差k他們必須爲在這種情況下的最佳結果。

如果max-min > k*n那麼它是非常容易： 設置

k=(max-min)/(n-1) 

在條件滿足的小數位數，並設置b[0]=min。將k添加到b的每個下一個元素。