如何找到最低成本？

Question

我試圖解決一個問題，其中包括尋找最低成本。這個問題可以表述爲：給定n建築物，併爲每個建築物的高度和成本給出。現在的任務是找到最低成本，使所有的建築物變成等於相同的高度。每棟建築物可以被認爲是垂直堆積的磚，其中每塊磚可以以與該建築物相關的成本來添加或去除。

例如： 假設n = 3的建築物的高度分別爲1,2,3和10,100,1000。

這裏，最低的成本將等於120

這裏是鏈接的問題：

http://www.spoj.pl/problems/KOPC12A/

一個明顯的答案是要找到與每個高度相關的成本對於所有的建築物，然後給他們輸出最小的成本。這是O（n^2）。

爲了尋找更好的解決方案，我試着找到高度與成本比值最小值的高度。然後所有的建築物必須等於這個高度並計算成本並作爲輸出。但是這給了我錯誤的回答。 這裏是我的實現：

基於下面的答案我已經使用加權平均值更新了我的代碼，但仍然沒有working.It給了我錯誤的答案。

#include<iostream> 
#include<cstdio> 
#include<cstdlib> 
#include<algorithm> 

using namespace std; 

long long fun(int h[],int c[],int optimal_h,int n){ 
    long long res=0; 
    for(int i=0;i<n;i++){ 
     res += (abs(h[i]-optimal_h))*c[i]; 
    } 
    return res; 
} 

int main() 
{ 
    int t; 
    cin>>t; 
    for(int w=0;w<t;w++){ 
     int n; 
     cin>>n; 
     int h[n]; 
     int c[n]; 
     int a[n]; 
     int hh[n]; 
     for(int i=0;i<n;i++){ 
      cin>>h[i]; 
      hh[i]=h[i]; 
     } 
     sort(hh,hh+n); 
     for(int i=0;i<n;i++) 
      cin>>c[i]; 

     long long w_sum=0; 
     long long cost=0; 

     for(int i=0;i<n;i++){ 
      w_sum += h[i]*c[i]; 
      cost += c[i]; 
     } 

     int optimal_h; 
     if(cost!=0){ 
      optimal_h=(int)((double)w_sum/cost + 0.5); 
      if(!binary_search(hh,hh+n,optimal_h)){ 
       int idx=lower_bound(hh,hh+n,optimal_h)-hh; 
       int optimal_h1=hh[idx]; 
       int optimal_h2=hh[idx-1]; 
       long long res1=fun(h,c,optimal_h1,n); 
       long long res2=fun(h,c,optimal_h2,n); 
       if(res1<res2) 
        cout<<res1<<"\n"; 
       else 
        cout<<res2<<"\n"; 
      } 
      else{ 
       long long res=fun(h,c,optimal_h,n); 
       cout<<res<<"\n"; 
      } 

     } 
     else 
      cout<<"0\n"; 
    } 

    return 0; 
} 

任何想法如何解決這個問題？

Answer 1

試着將高度視爲價值和成本，以確定性，重要性。

簡單的加權平均應該在這裏做的伎倆：

costsum=0; 
weightedsum=0; 
for(int i=0; i<n; ++i) 
{ 
    costsum += c[i]; 
    weightedsum += h[i]*c[i]; 
} 

optimalheight = round(double(weightedsum)/costsum); 

然後不計成本知道最佳高度：

cost=0; 
for(int i=0; i<n; ++i) 
    cost += c[i] * abs(h[i] - optimalheight); 

Answer 2

這裏是要求建築物高度進行排序劑（I」 m將從最短到最高）。如果數據已經排序，那麼這應該在O（N）時間內運行。

設k是所有建築物的高度，所以我們想要找到最優的k。 調整所有這些建築的成本爲：

M = Sum(|k-hj|cj, j from 0 to N). 

現在，因爲他們進行排序，我們可以找到一個索引i使得對所有的j < = I，HJ < = k和對於所有的j>我， hj> k。 這意味着我們可以重寫我們的成本公式爲：

M = Sum((k-hj)cj, j = 0 to i) + Sum((hj-k)cj, j = i+1 to N). 

現在，我們將通過最短的和高樓之間的k值迭代，直到我們找到了一個成本最低（我們將進一步往下看的是我們沒有檢查每一個） 計算在每次迭代的成本爲N操作，所以我們會發現我們的成本函數的遞歸定義來代替：

M(k+1) = Sum((k+1-hj)cj, j = 0 to p) + Sum((hj-k-1)cj, j = p+1 to N). 

我們可以將「1」條款出的款項得到：

M(k+1) = Sum((k-hj)cj, j = 0 to p) + Sum((hj-k)cj, j = p+1 to N) + Sum(cj, j = 0 to p) - Sum(cj, j = p+1 to N). 

現在p是新的i，並且有2種可能的情況：p = i或p = i + 1。 如果P = I：

M(k+1) = M(k) + Sum(cj, j = 0 to p) - Sum(cj, j = p+1 to N) 

和如果p = i + 1的

M(k+1) = M(k) + Sum(cj, j = 0 to p) - Sum(cj, j = p+1 to N) + 2(k+1 - h(i+1))c(i+1). 

在P = I我們實際上可以發現M（K + M）的情況下直接從M（k）的因爲在每一次迭代，我們只增加一個常數項（在K即換算常數），所以如果p = I：

M(k+m) = M(k) + m(Sum(cj, j = 0 to p) - Sum(cj, j = p+1 to N)). 

這意味着我們的功能構成的迭代之間的直線，其中i是恆定的。由於我們感興趣的是當我們的功能從減少到增加，這在所有這些迭代中間都不會發生。它只能發生在我增加（p = i + 1）或第一步之後（因爲該行不同於前一行）。 從什麼到這裏爲止的算法會去是這樣的：

1. 排序的高度，如果必要的（O（NlogN））
2. 初始化您4個款項（兩個和在M（k）和兩個附加併購金額介紹（K + 1））（O（N））

3. 迭代通過你的高度，這樣的（O（N）），當您去尋找最小值：

   - 增加k以高度下一個最高的建築物減去一個（使用M（k + m）），看看這是否代表新的最小值

   - 通過改變i值來增加k，看看是否代表新的最小值

4. 打印出答案。

還有一些其他優化可能在這裏，我還沒有想太多。 顯而易見的是每當我改變時不重新計算你的款項。

我很抱歉，如果數學很難讀，我是新的StackOverflow，並沒有想出所有可能的格式。

我沒有任何代碼來支持這個，所以我希望這已經足夠好了。

Answer 3

我最近遇到了一個類似的問題，最小的區別就是在我的問題中，只能將樓層添加到建築物中，不能刪除它。但這個想法應該是相似的。隨時給我留下任何意見或問題。

我認爲處理此問題的一個好方法是： 首先對輸入進行排序，這通常可以通過Java中的語言內置API調用完成，我使用Arrays.sort（）。這通常是nLog（n）時間複雜度。 排序後，我們可以在窗口內維護一個大小爲m的窗口，我們可以計算每個窗口的最小代價，而我們將窗口從開始移動到結束，我們計算並更新全局最小代價。 這裏的實現：

static long minFloors(long[] buildings, int m) { 
     //sort buildings 
     Arrays.sort(buildings); 
     //maintain a window of size m, compute the minCost of each window, update minCost along the way as the final result 
     long minCost = Long.MAX_VALUE; 
     for(int i = 0; i <= buildings.length-m; i++){ 
      long heightToMatch = buildings[i+m-1]; 
      if(heightToMatch == buildings[i]) return 0;//if the last building's height equals the first one, that means the whole window if of the same size, we can directly return 0 
      long thisCost = 0; 
      for(int j = i+m-1; j >= i; j--){ 
       thisCost += heightToMatch - buildings[j]; 
      } 
      minCost = Math.min(minCost, thisCost); 
     } 
     return minCost; 
    } 

而且我分享我的解決方案在這裏：如果您使用[標籤：C++]： Space Rock question