我正试图解决一个问题，该问题包括找到最小成本。这个问题可以表述为：给定n栋建筑，每栋建筑的高度和成本都是给定的。现在的任务是找到最小的成本，使所有的建筑都达到相同的高度。每栋建筑都可以被视为一堆垂直的砖块，在那里，每块砖块都可以添加或移除，成本与该建筑相关。
例如：假设有n=3栋建筑，高度分别为1,2,3和101001000。
在这里，最低成本将等于120。
以下是问题的链接：
http://www.spoj.pl/problems/KOPC12A/
一个显而易见的答案是找到与所有建筑的每个高度相关的成本，然后给出它们的最小成本作为输出。这是O（n^2）。
为了寻找更好的解决方案，我试图找到高度/成本比最小的高度。然后所有建筑都必须等于这个高度，计算成本并作为输出。但这给了我错误的答案。这是我的实现：
基于以下答案，我已经使用加权平均值更新了我的代码，但仍然不起作用。它给了我错误的答案。
#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<<"0n";
}
return 0;
}
知道怎么解决这个问题吗？
试着把高度看作价值，把成本看作确定性和重要性。
简单加权平均应该在这里发挥作用：
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);
这里有一个需要对建筑高度进行排序的解决方案（我将假设从最短到最高）。如果数据已经排序，那么这应该在O（N）时间内运行。
设k是所有建筑物的高度，所以我们想找到最优的k。调整所有这些建筑的成本由给出
M = Sum(|k-hj|cj, j from 0 to N).
现在，因为它们被排序，我们可以找到索引i，使得对于所有j<=i、 hj<=并且对于所有j>i，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，有两种可能的情况：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（k+M），因为在每次迭代中，我们只添加一个常数项（即k的常数），所以如果p=i：
M(k+m) = M(k) + m(Sum(cj, j = 0 to p) - Sum(cj, j = p+1 to N)).
这意味着我们的函数在迭代之间形成一条直线，其中i是常数。由于我们对函数从减少到增加的时间感兴趣，所以在所有这些迭代的中间不可能发生这种情况。它只能在i递增（p=i+1）或之后的第一步时发生（因为线与通向它的线不同）。从目前的情况来看，算法会像这样：
- 必要时对高度进行排序（O（NlogN））
- 初始化你的4个和（M（k）中的两个和和M（k+1）中引入的两个附加和）（O（N））
像这样迭代你的高度（O（N）），在你前进的过程中找到最小值：
-将k增加到下一个最高建筑的高度减去1（使用M（k+M）），看看这是否代表新的最小
-将k增加一，改变i值，看看这是否代表新的最小
- 打印出答案
这里还有一些其他可能的优化，我还没有想太多。显而易见的是，每当我改变时，不要重新计算你的总和。
如果数学很难阅读，我很抱歉，我是StackOverflow的新手，还没有弄清楚所有可能的格式。
我没有任何代码来支持这一点，所以我希望这已经足够好了。
我最近遇到了一个类似的问题，小的区别是，在我的问题中，只能为建筑物增加楼层，而不能将其移除。但想法应该相似。请随时给我留言或提出任何问题。
我认为解决这个问题的一个好方法是：首先对输入进行排序，这通常可以通过语言内置的API调用来完成，在Java中，我使用了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;
}
我还在这里分享了我的解决方案：太空摇滚问题