Geek asks and answers

Search for the total height of buildings with minimal cost

This is a question from some programming contest (I don’t know exactly what programming it refers to, I saw it a year ago). The question is this:

There are N buildings, each of which has its own height (not necessarily unique)

{h1,h2,h3,...,hn}

We must make all buildings of the same height say h.

Allowed operations:

  • We can add some height to the building.
  • We can remove some height from the building.

For each building, there is a cost associated with removing / adding unit height. Let's say c (i) will cost to remove / add unit height to the building. Relevant costs are as follows:

{c1,c2,c3,...,cn}

, (), , .

Input: N . (1 <= N < 100000). .

{h1,h2,h3,...,hn}


 {c1,c2,c3.....,cn}

.

:

3

2 1 3

10 1000 1


12

: 1, 10 * (2-1) + 1000 * (1-1) + 1 * (3-1) i.e 12.

, O (n ^ 2).

, , :

h,

 {h1,h2,h3,....,hn}

. h h (i). , h (i), O (n ^ 2).

?

+5
2

O (n log (n)) :

h (i) i- c (i) i- .

  • -1: . P. i.e P (1) - , P (n) - . O (n log n).
  • -2: . S . O (n).
  • 3: Cost_of_Increase (i) , , , i- , i- SORTED ARRAY P, Cost_of_Increase (i) P (i-1), P (i-2),... P (n), P (i).

:

Cost_of_Increase (i) = Cost_of_Increase (i-1) + (h (i) -h (i-1)) * ( P (i-1) - P (n) - )

, i-1 P, .

Cost_of_decrease (i) , , , i- , i- SORTED ARRAY P, Cost_of_decrease (i), P (1), P (2),... P (i-2), P (i-1), P (i) - .

:

Cost_of_decrease (i) = Cost_of_decrease (i + 1) + (h (i + 1) -h (i)) * ( P (1) - P (i-1) - )

, , P (i), :

Cost_of_Increase (i) + Cost_of_decrease (i).

, , , .

, !

+2

. , O (N * log (H)), H - .

: , ( , )

  typedef long long ll;
  ll get_cost(int h) {
    if (h < 0 || h > MAX_HEIGHT) {
      return MAX_VAL; // some unreachable positive value
    }
    ...
  }


  int main() {
    ...
    int current = 0;
    int leftp, rightp;
    ll cv, lv, rv;
    ll step = SOME_BIG_ENOUGH_VALUE;
    while (step > 0) {
      leftp = current - step;
      rightp = current + step;
      cv = get_cost(current);
      lv = get_cost(leftp);
      rv = get_cost(rightp);
      if (cv <= rv && cv <= lv) {
        step /= 2;
      } else if (lv < rv) {
        current = leftp;
      } else {
        current = rightp;
      }
    }
    ...
  }
+1

More articles:


All Articles