如何找到最低成本？

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