Building Construction#10869

Building Construction (Editorial)

Sort the buildings by height so that $h_{1} \leq h_{2} \leq ... \leq h_{n}$ h_1 \le h_2 \le ... \le h_n. Buildings with the same heights are sorted by increasing cost of adding / removing.

Find the cost for which we can make the height of all houses equal to $h_{x} (1 \leq x \leq n)$ h_x~(1 \le x \le n). It is equal

f (x) = i = 1 \sum n ∣ h_{i} - h_{x} ∣ \cdot c_{i}

f(x) = \sum_{i=1}^n |h_i - h_x| \cdot c_i

The function $f (x)$ is concave and has a global minimum, that can be found with a ternary search.

Example

Consider the first example. Sort buildings by height:

Find the value of the function $f (x)$ for all heights:

$f (1) = (1 - 1) \cdot 30 + (2 - 1) \cdot 10 + (3 - 1) \cdot 20 + (4 - 1) \cdot 40 = 170$ f(1) = (1 - 1) \cdot 30 + (2 - 1) \cdot 10 + (3 - 1) \cdot 20 + (4 - 1) \cdot 40 = 170,
$f (2) = (2 - 1) \cdot 30 + (2 - 2) \cdot 10 + (3 - 2) \cdot 20 + (4 - 2) \cdot 40 = 130$ f(2) = (2 - 1) \cdot 30 + (2 - 2) \cdot 10 + (3 - 2) \cdot 20 + (4 - 2) \cdot 40 = 130,
$f (3) = (3 - 1) \cdot 30 + (3 - 2) \cdot 10 + (3 - 3) \cdot 20 + (4 - 3) \cdot 40 = 110$ f(3) = (3 - 1) \cdot 30 + (3 - 2) \cdot 10 + (3 - 3) \cdot 20 + (4 - 3) \cdot 40 = 110,
$f (4) = (4 - 1) \cdot 30 + (4 - 2) \cdot 10 + (4 - 3) \cdot 20 + (4 - 4) \cdot 40 = 130$ f(4) = (4 - 1) \cdot 30 + (4 - 2) \cdot 10 + (4 - 3) \cdot 20 + (4 - 4) \cdot 40 = 130

The minimum of the function $f (x)$ is achieved at $x = 3$ x = 3, while $f (3) = 110$ f(3) = 110.

Algorithm implementation

Each building has a height $h$ and the cost $cos t$ of adding or removing a floor. The information about all buildings is stored in the array $b$ .

#define MAX 100001
struct Building
{
  int h, cost;
};
Building b[MAX];

The function cmp is a comparator for sorting buildings. Buildings are sorted by increasing height. If the heights of the buildings are the same, then sort them by increasing cost.

int cmp(Building a, Building b)
{
  if (a.h == b.h)
    return a.cost < b.cost;
  return a.h < b.h;
}

The function f computes the cost to make all buildings equal to the height of the building number $x$ .

long long f(int x)
{
  long long ret = 0;
  for (int i = 1; i <= n; i++)
    ret += 1LL * abs(b[x].h - b[i].h) * b[i].cost;
  return ret;
}

C++

The function ternary_search uses the ternary search to find the value of $x \in [l e f t; r i g h t]$ x \in [left; right] for which $f (x)$ is minimal. Initially, the search range is $[l e f t; r i g h t] = [1; n]$ [left; right] = [1; n].

long long ternarySearch(int left, int right)
{
  while (right - left >= 3)
  {
    int a = left + (right - left) / 3;
    int b = left + 2 * (right - left) / 3;
    if (f(a) > f(b))
      left = a;
    else
     right = b;
  }

C++

The difference between $l e f t$ and $r i g h t$ does not exceed $3$ . In this case, the minimum of $f (x)$ on the interval $[l e f t; r i g h t]$ [left; right] is found by exhaustive search.

  long long res = f(left++);
  while (left <= right)
    res = min(res, f(left++));
  return res;
}

The main part of the program. Read the input data.

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%d", &b[i].h);
for (i = 1; i <= n; i++)
  scanf("%d", &b[i].cost);

Sort the buildings.

sort(b + 1, b + n + 1, cmp);

Find and print the answer. Buildings are numbered from $1$ to $n$ .

printf("%lld\n", ternarySearch(1, n));