從一組整數中選取若干個數，如何使得它們的平均數與中位數之差最大？

1樓：

陣列長度為奇數時找最小的數當中位數，其餘的數為依次最大的數。從陣列長度為3開始，依次從剩餘的數中抽最大的數放進來，因為此時的平均數趨勢是先增加再減少的，所以取極值就是最優。

陣列長度為偶數時找最小的兩個放中間，其餘的與奇數同理。從陣列長度為4開始。

當陣列長度為2時，無論是取最大最小還是兩個最小都無所謂，因為差都是0。

2樓：

首先我們能判斷出所選的這些數的個數一定是奇數，因為偶數的話，若我們去掉中間那兩個數中較大的乙個，所得的解是不會變差的。那麼就可以推出中位數一定是原先數列中的某乙個數。我們來列舉這個中位數，然後再在二分的找選出的數的長度l，當平均數最大時找到的數一定是中位數右邊最大的a[n - l / 2+ 1 :

n]和a[i - l / 2 : i]（中位數為a[i]時），那麼處理l/2即可。由於此平均數為先增大後減小，那麼二分則是沒有問題的。

3樓：

感覺這題很智障啊，當然也有可能是我智障。

說思路，中位數小於平均數的情況，盡量使得中位數小，而平均數大，假設取5個數。那麼我們先取陣列的最小的三個數(中位數盡可能小)，現在要使平均數盡可能大了，剩下的兩個數取最大的數。中位數大於平均數的情況同理，然後比較兩種情況哪個更優，得解。

用反證法似乎可以證明這個理論。

補充，也有可能我理解錯了，取的數數量不固定，但是即使這樣，也可以先給陣列排序，然後遞推1-n個數的最優解。複雜度都落在排序上了

4樓：Meiku Kazami

首先想最優解中中位數只能是原數列中的數或原數列中相鄰兩個數的平均值，不然最中間的兩個數總可以向乙個方向靠攏使得解不變差。

列舉中位數後是貪心成對取小於中位數的最小值，和大於中位數的最小值的過程。因此二分就可以了。