Будівельна конструкція#10869

Будівельна конструкція (Розбір)

Відсортуємо будівлі за їх висотами так, щоб виконувалася нерівність: $h_{1} \leq h_{2} \leq ... \leq h_{n}$ h_1 \le h_2 \le ... \le h_n. Якщо декілька будівель мають однакову висоту, упорядкуємо їх додатково за зростанням вартості додавання або видалення цегли.

Розглянемо вартість, необхідну для того, аби привести всі будівлі до висоти $h_{x} (1 \leq x \leq n)$ h_x~(1 \le x \le n). Вона дорівнює

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

Функція $f (x)$ , яка описує цю вартість, є ввігнутою і має глобальний мінімум, котрий можна знайти за допомогою тернарного пошуку.

Приклад

Розглянемо перший приклад. Відсортуємо будівлі за їх висотами:

Знайдемо значення функції $f (x)$ для всіх можливих висот будівель:

$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

Мінімальне значення функції $f (x)$ досягається при $x = 3$ x = 3; у цьому випадку $f (3) = 110$ f(3) = 110.

Реалізація алгоритму

Кожна будівля має висоту $h$ і вартість $cos t$ додавання або видалення одного поверху. Інформація про будівлі зберігається в масиві $b$ .

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

Функція cmp є компаратором для сортування будівель. Спершу будівлі сортуються за зростанням висоти, а при рівних висотах — за зростанням вартості.

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

Функція f обчислює вартість, необхідну для того, аби зробити всі будівлі однакової висоти з висотою будівлі номер $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++

Функція ternary_search за допомогою тернарного пошуку шукає таке значення $x \in [l e f t; r i g h t]$ x \in [left; right], при якому $f (x)$ мінімальна. Спочатку границі діапазону задані як $[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++

Різниця між $l e f t$ і $r i g h t$ не перевищує $3$ . У цьому випадку мінімальне значення $f (x)$ на відрізку $[l e f t; r i g h t]$ [left; right] знаходимо повним перебором.

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

Основна частина програми. Читаємо вхідні дані.

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(b + 1, b + n + 1, cmp);

Обчислюємо і виводимо відповідь. Будівлі нумеруються від $1$ до $n$ .

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