我發現了一個貪心演算法問題，我們必須找到最小值。使人們坐在一起所需的跳躍次數。
這是文章的鏈接以供參考。
文章中的問題描述：
標題：
使一群人坐在一起所需的最少跳躍次數。描述：
給定一個長度為 N 的字串 S，由 'x' 和 '.' 組成。給定的字串代表一排座位，其中有“x”和“.”。分別代表已占用和未占用的座位。任務是最小化跳躍或跳躍的總數，以使所有乘員坐在一起，即彼此相鄰，而他們之間沒有任何空位。例子：
輸入：S =“。. . . X 。. XX。. . X 。。”
輸出：5
解釋：讓第 5 個座位??的人跳 2 個位置到第 7 個座位。使第 13 位的人跳 3 個位置到第 10 位。因此，所需的總跳躍次數 = 2 3 = 5。輸入：S = “xxx . . . . . . . . xxxxxx”
輸出：24
解釋：將乘員分別從第 1、第 2、第 3 個位置移動到第 9、第 10、第 11 個位置。因此，所需的總跳躍次數 = (11 – 3) (10 – 2) (9 – 3) = 24。
方法：
這個想法是使用貪婪方法來解決這個問題。觀察到將元素移向人中的中間元素或所有在場的人中的中心人總是最優的。當我們將點移到中位數時，跳躍的次數總是最少的。
貪婪的解決方案是將元素移向中位數。但沒有找到這方面的證據。是否存在使用這種方法的一些數學證明？
uj5u.com熱心網友回復：
設a[i]人員的初始位置i（基于 0 的索引），其中人員的順序設定為按位置增加的順序，并n作為人員計數。假設所有人連續坐下的最后一個位置區間從位置 開始t。由于人的相對順序沒有改變，我們看到人i從 移動a[i]到t i。這種移動何時以及如何發生對我們來說并不重要，但從來不需要一個人在遠離其目標位置的方向上跳躍，因此它會產生|a[i] - (t i)| == |t - (a[i] - i)| == |t - b[i]|跳躍，其中b由 定義b[i] = a[i] - i，是一個非遞減陣列，因為a它是嚴格遞增的（因此b[i 1] - b[i] == a[i 1] - (a[i] 1) >= 0）。
因此，從位置開始的結果間隔的最小跳躍總數t是total[t] = sum(i, |t - b[i]|)。現在，d_total[t] = total[t 1] - total[t] == sum(i, |t - b[i] 1| - |t - b[i]|) == sum(i, t >= b[i] ? 1 : -1) == count(i, t >= b[i]) - count(i, t < b[i]) == 2*count(i, t >= b[i]) - n是 的“離散導數” total，很容易看出隨著t增加，d_total[t]它是非減少的，在t == b[i]某些點上i增加2*count(i, t == b[i])。的最小值total發生在t為d_total[t]正的最小值處（這意味著count(i, t >= b[i]) > n/2）。
特別是，對于奇數n == 2*k 1，t恰好是 的中位數b，而結果區間的“中心”是t k == b[k] k == a[k]，即 的中位數a，如解中所假設的那樣。因為即使n == 2*k我們有包含區間tbetweenb[k - 1]和b[k]wheretotal[t]是最小的（d_total[t] == 0for t ? [b[k - 1]; b[k] - 1]and t == b[k]is the minimum where d_total[t] > 0），這意味著結果區間的“左中心”是t k - 1 ? [a[k - 1]; a[k] - 1]（或者，等效地，“右中心” t k ? [a[k - 1] 1; a[k]]），所以我們有幾個最優解在這個如果a[k] > a[k - 1].
在任何情況下，如我們所見，最佳策略是跳向中位數（或偶數n情況下的“中位數區間”，但由于中位數隨后被定義為該區間兩端的平均值，我們仍然可以說“向中位數方向” ) 的起始人員職位。
最后，也許這很明顯，但為了完整性：請注意，獲得的全域最小值t不會產生超出輸入字串的區間，因為在兩種奇偶校驗情況下很容易證明a[0] <= t <= t n - 1 <= a[n - 1]， 和a元素是該字串的位置。所以，這個全域最小值總是適合我們的目的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/492026.html