Clever Geek Handbook

How do I find the minimum cost?

I am trying to solve a problem which is to find the minimum cost. The problem can be formulated as follows: Given that there are n buildings and for each building its height and cost are given. Now the challenge is to find the minimum cost so that all buildings become equal to the same height. Each building can be thought of as a vertical brick pile, where each brick can be added or removed with a value associated with that building.

For example: Let's say there are n = 3 buildings with a height of 1,2,3 and a cost of 10,100,000 respectively.

Here the minimum cost will be 120.

Here is a link to the problem:

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

The obvious answer is to find the cost associated with each of the heights for all buildings, and then give the minimum cost of them as an output. It's O (n ^ 2).

Looking for a better solution, I tried to find the height with the minimum value for the height / cost ratio. Then all buildings must be equal to this height and calculate the cost and give as an output. But that gives me the wrong answer, Here is my implementation:

Based on the answers below, I updated my code using a weighted average but still not working. He gives me the wrong answer.

#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;
}

Any ideas how to solve this?

+3


source to share


3 answers


Try to think of heights as values ​​and costs as certainty, significance.

A simple weighted average should do the trick here:

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

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


Then calculate the cost, knowing the optimal height:

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


source


Here is a solution that requires sorting the heights of the building (I'm going to go from shortest to tallest). If the data is already sorted, then this should be done in O (N) time.

Let k be the height of all buildings, so we want to find the optimal k. The cost of adjusting all these buildings is determined by:

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

Now, since they are sorted, we can find an index i such that for all j <= i, hj <= k and for all j> i, hj> k. This means that we can rewrite our cost equation as follows:

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

We will now iterate over the k values ​​between the shortest and tallest building until we find the one with the lowest cost (we will see further that we do not need to check each one) Calculating the cost at each iteration is N operations, so instead we find a recursive definition of our cost function:

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

We can move "1" out of the sum to get:

    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).

Now p is the new i, and two cases are possible: p = i or p = i + 1.if p = i:



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

and if 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).

In the case where p = i, we can actually find M (k + m) directly from M (k), because at each iteration we only add a constant term (constant in terms of k, which is), so if p = I am:

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

This means that our function forms a straight line between iterations where I am constant. Since we are interested in when our function goes from decreasing to increasing, this cannot happen between the middle of all these iterations. This can only happen when i increases (p = i + 1) or in the first step after (since the line is different from the line leading to it). From what is here so far, the algorithm would look something like this:

  • Sort the height as needed (O (NlogN))
  • Initialize your 4 sums (two sums in M ​​(k) and two additional sums entered in M ​​(k + 1)) (O (N))

  • repeat your heights like this (O (N)), find the min value as you go:

    -Increase k to the height of the next tallest building less than one (using M (k + m)) and see if this represents a new minimum

    -Increase k with one change in i and see if this represents a new minimum

  • Print out the answer.

There are some other optimizations possible here that I haven't thought too much about yet. The obvious is not to recalculate your amounts every time I change.

Apologies if the math is hard to read, I am new to StackOverflow and have not understood every possible format.

I don't have any code to support this, so I hope it works well enough.

0


source


I recently came across a similar question, but the slight difference is that in my question it is possible to add floors to a building, you cannot remove it. But the idea should be similar. Feel free to leave me comments or questions.

I think one good way to approach this question: First sort the input first, this can usually be done with built-in API calls, in Java, I used Arrays.sort (). This is usually the time complexity of nLog (n). After sorting, we can keep the window of size m, inside the window, we could calculate the minimum cost for each window, while we slide the window from start to end, we calculate and update the global minimum cost. Here's the implementation:

    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 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;
    }

Also I shared my solution here: Space Rock Question

0


source






More articles:


All Articles