以最低成本找到建築物的常見高度

Question

這是一些編程比賽的問題（我不清楚它屬於哪個編程比賽，我在一年前見過）。現在的問題是：

有N個建築，每個都具有其自身的高度（不一定是唯一的）

{h1,h2,h3,...,hn} 

我們必須同樣高度的所有建築物說小時。

允許的操作是：

1. 我們可以添加一些高度建築物。
2. 我們可以從建築物中移除一些高度。

每個建築物移除/增加一個單位高度都有相關成本。說c（i）是向建築物移除/增加單位高度的成本。相應的成本如下：

{c1,c2,c3,...,cn} 

假設我們有足夠的高度（單位）可用，我們必須找到它，使同一高度的所有建築物所需的最小成本。

輸入： 第一行將指定N個建築物的數量。 （1 < = N < = 100000）。 第二行輸入將用於建築物的高度。

{h1,h2,h3,...,hn} 

輸入的第三行將使成本陣列

{c1,c2,c3.....,cn} 

輸出

的輸出將是簡單地需要的最小代價。

樣品輸入：

3 

2 1 3 

10 1000 1 

樣本輸出

12 

說明：讓身高1的所有建築，因此成本會 10 *（2-1）+ 1000 *（ 1-1）+ 1 *（3-1）即12.

我知道蠻力的方法是O（n^2）。

蠻力方法我認爲是如下：

無論公共高度h是，它必須是從

{h1,h2,h3,....,hn} 

即ħ必須等於任何的H（i）中。 現在檢查每個h（i）我可以計算O（n^2）中的答案。

它可以做得更快嗎？

Answer 1

O（N日誌（n））的解決方案：

設h（i）表示第i棟建築物的高度，並且令c（i）表示第i棟建築物的成本。

1. 步驟-1：按照遞減的順序的各建築物的高度排序建築物。讓這種安排被稱爲P，即P（1）是最大建築物的高度，P（n）是最小建築物的高度。這需要O（n log n）。
2. 步驟2：總建築全部高度。讓S表示這個總和。這一步需要O（n）次。步驟3：如果我們使所有高度小於第i個建築物的所有建築物的高度等於排序陣列P中第i個建築物的高度，即Cost_of_Increase（i），則使Cost_of_Increase（i）表示Cost如果我們把建築物P（I-1），P（I-2），... P（N）等於P（i）個建築物的高度。

現在使用這種遞推：

Cost_of_Increase（ⅰ）= Cost_of_Increase第（i-1）+（H（ⅰ）-H（I-1））*的P的成本（薩姆（異1）個建築物至P（N）個builing）

注意，在上述的遞歸i和i-1的順序是根據P的順序，即按排序順序。

現在讓Cost_of_decrease（i）表示如果我們使所有高度大於第i個建築物的建築物等於第S個建築物在排序陣列P中的高度，即Cost_of_decrease（i）建築物P（1），P（2），... P（I-2），P（I-1）等於P（i）個建築物的高度。

對於此用途這種遞推：

Cost_of_decrease（ⅰ）= Cost_of_decrease第（i + 1）+（H（I + 1）-h（I））*（薩姆P的成本的（1）個建築物爲P（I-1）個建築物）

用於製造所有等於P（i中的建築物的高度，使總成本）個建築物是：

Cost_of_Increase（ⅰ）+ Cost_of_decrease（i）中。

一旦我們有了這個對所有的建築物，只是檢查哪一個成本最小，這就是答案。

希望它有幫助！

Answer 2

做一個ternary search或使用hill climbing算法算法結束後的所有建築物的高度。對於每個高度，您可以計算線性時間的成本，因此總體複雜度將爲O（N * log（H）），其中H是可能的最大高度。

編輯：這裏是一個僞代碼段應該爲你工作（這是爬坡式的方法）

typedef long long ll; 
    ll get_cost(int h) { 
    if (h < 0 || h > MAX_HEIGHT) { 
     return MAX_VAL; // some unreachable positive value 
    } 
    ... 
    } 


    int main() { 
    ... 
    int current = 0; 
    int leftp, rightp; 
    ll cv, lv, rv; 
    ll step = SOME_BIG_ENOUGH_VALUE; 
    while (step > 0) { 
     leftp = current - step; 
     rightp = current + step; 
     cv = get_cost(current); 
     lv = get_cost(leftp); 
     rv = get_cost(rightp); 
     if (cv <= rv && cv <= lv) { 
     step /= 2; 
     } else if (lv < rv) { 
     current = leftp; 
     } else { 
     current = rightp; 
     } 
    } 
    ... 
    }