如何找到最低成本？
我正在尝试解决一个由寻找最小cost.The问题组成的问题可以表述为:给定n个建筑物，对于每个建筑物，它的高度和费用是given.Now，任务是找到最小费用，使得所有建筑物变得相同height.Each建筑物可以被视为垂直的砖堆，其中每一块砖可以随着与该建筑物相关的费用而增加或移除。
例如:假设有高度为1,2,3的n=3建筑物，成本分别为10,100,1000。
这里，最低成本将等于120。
以下是问题的链接：
http://www.spoj.pl/problems/KOPC12A/
一个显而易见的答案是找到与所有建筑物的每个高度相关的成本，然后给出them.This的最小成本为O(n^2)作为输出。
为了寻找更好的解决方案，我试着找出高度/成本比最小的高度，然后所有的建筑物都必须等于这个高度，并计算成本并给出output.But，这给了我错误的答案。下面是我的实现：
基于下面的答案，我已经使用加权平均更新了我的代码，但仍然不能工作，这给了我错误的答案。
#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;
}你知道怎么解决这个问题吗？
回答 3
Stack Overflow用户
发布于 2012-03-21 01:28:48
试着把高度看做价值，把成本看做确定性和重要性。
简单的加权平均应该可以做到这一点：
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);Stack Overflow用户
发布于 2012-03-21 11:37:34
这是一个需要对建筑物高度进行排序的解决方案(我将假设从最短到最高)。如果数据已经排序，那么这应该在O(N)时间内运行。
假设k是所有建筑物的高度，所以我们想要找到最优的k。调整所有这些建筑物的成本由下式给出：
M = Sum(|k-hj|cj, j from 0 to N).现在因为它们是排序的，所以我们可以找到一个索引i，使得对于所有j <= i，hj <= k和对于所有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)或之后的第一步(因为该行与通向它的行不同)时才会发生这种情况。从这里到目前为止，算法是这样的：
对4个(O(NlogN))
- Initialize ( M(k)中的两个和和M(k+1)中引入的两个和)在高度中进行排序，如有必要，请按如下所示(O(N))查找最小值：
将k减去下一个最高建筑物的高度(使用M(k+m))，并查看这是否表示一个新的最小值
通过更改i值来输出k，并查看这是否代表新的minimum
- Print -Increase答案。
这里还有一些其他可能的优化，我还没有过多地考虑。显而易见的一点是，每当我更改时，不要重新计算您的总和。
如果数学很难读，我很抱歉，我是StackOverflow的新手，还没有弄清楚所有可能的格式。
我没有任何代码支持这一点，所以我希望这是足够好的。
Stack Overflow用户
发布于 2016-08-29 02:10:04
我最近遇到了一个类似的问题，最小的区别是，在我的问题中，只能为建筑物增加楼层，而不能将其移除。但想法应该是相似的。请随时给我留下任何评论或问题。
我认为解决这个问题的一个好方法是:首先对输入进行排序，这通常可以通过语言内置的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;
}我还在这里分享了我的解决方案： Space Rock question
https://stackoverflow.com/questions/9791296
复制相似问题
腾讯云开发者
