最大化最小差異

-2

我們給出N個元素形式的數組A，現在我們必須從N個給定索引中選擇K個索引，這樣對於任何2個索引i和j，| A [i] -A [j ] |儘可能大。我們需要告訴這個最大值。舉個例子：假設N = 5，K = 2，數組爲[1,5,3,7,11]，那麼這裏的答案是10，因爲我們可以簡單地選擇第一個和最後一個位置，並且不同= 11- 1 = 10。例如，設N = 10，K = 3，數組A爲[3 9 6 11 15 20 23]，那麼這裏的答案將爲8.因爲我們可以選擇[3,11,23]或[3， 15,23]。最大化最小差異

現在給定N，K和陣列A，我們需要找到這個最大差異。

我們給出一個1≤N≤10^5和1≤小號≤10^7

來源

2015-03-02 user3840069

讓我們對數組進行排序。
現在我們可以對答案進行二分查找。
對於一個固定的候選人x，我們可以選擇貪婪的元素（遍歷排序後的數組，如果可能的話每個元素）。如果我們挑選的元素數量不小於K,x是可行的。否則，它不是。

時間複雜度爲O(N * log N + N * log (MAX_ELEMENT - MIN_ELEMENT))

的僞代碼：

bool isFeasible(int x): 
    cnt = 1 
    last = a[0] 
    for i <- 1 ... n - 1: 
     if a[i] - last >= x: 
      last = a[i] 
      cnt++ 
    return cnt >= k 

sort(a) 
low = 0 
high = a[n - 1] - a[0] + 1 
while high - low > 1: 
    mid = low + (high - low)/2 
    if isFeasible(mid): 
     low = mid 
    else 
     high = mid 
print(low)

來源

2015-03-02 19:04:03 kraskevich

你可以提供算法的僞代碼 – user3840069 2015-03-02 19:05:10

@ user3840069我剛剛添加它。 – kraskevich 2015-03-02 19:13:17

爲什麼是可能的（int x）：因爲您沒有在任何地方使用x – user3840069 2015-03-02 19:16:15

我認爲這可以作爲一個動態規劃問題進行處理。首先排序A，然後問題是在A中標記K個元素，使得相鄰標記項之間的最小差異儘可能大。作爲初學者，您始終可以標記第一個和最後一個元素。

從左到右移動，在i = 1..N的每個位置，通過在終止於此位置的子數組中標記i元素，可以獲得最大的最小差異。您可以計算終止於此位置的k個物品的最大最小差異，方法是考慮終止於您所處位置左側每個位置的k-1個物品的最大最小差異。最明顯的做法是考慮每個可能的位置，直到您當前正在處理的位置，以最小差異結束一段k-1項目，但您可以在此處執行二進制搜索以加快速度。

一旦你一直工作到右手端，你知道原始問題的最大可能值。如果您需要知道K元素的放置位置，您可以隨時記錄筆記，以便您可以回溯找出導致此解決方案的所選元素，從右向左工作。

來源

2015-03-02 19:08:41 mcdowella

最大化最小差異

回答

相關問題