Tikinti konstruktoru#10869

Tikinti konstruktoru (Həll təhlili)

Binaları onların hündürlüyünə görə çeşidləyək, belə ki $h_{1} \leq h_{2} \leq ... \leq h_{n}$ h_1 \le h_2 \le ... \le h_n bərabərsizliyi ödənilsin. Əgər bir neçə bina eyni hündürlüyə malikdirsə, onları əlavə və ya çıxarmaq qiymətinə görə azalan şəkildə də sıralayırıq.

Bütün binaları $h_{x} (1 \leq x \leq n)$ h_x~(1 \le x \le n) hündürlüyə gətirmək üçün lazım olan qiyməti nəzərdən keçirək. O, bərabərdir

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

Bu qiyməti təsvir edən $f (x)$ funksiyası qapalı və qlobal minimuma malikdir ki, bu da üçlük axtarışı ilə tapıla bilər.

Nümunə

İlk nümunəni nəzərdən keçirək. Binaları onların hündürlüyünə görə çeşidləyək:

Binaların mümkün bütün hündürlükləri üçün $f (x)$ funksiyasının qiymətlərini tapaq:

$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)$ funksiyasının minimum qiyməti $x = 3$ x = 3 olduğu halda əldə edilir; bu halda $f (3) = 110$ f(3) = 110.

Alqoritmin tətbiqi

Hər bir bina $h$ hündürlüyünə və mərtəbəni əlavə və ya çıxarmaq üçün $cos t$ xərci var. Bina məlumatları $b$ massivində saxlanılır.

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

cmp funksiyası binaların çeşidlənməsi üçün komparator rolunu oynayır. İlk növbədə binalar hündürlüklərə görə artan şəkildə, eyni hündürlükdə olan binalar isə xərclərinə görə çeşidlənir.

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

f funksiyası bütün binaları $x$ bina ilə eyni hündürlüyə gətirmək üçün lazım olan qiymətləri hesablayır.

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 funksiyası üçlük axtarışı vasitəsilə $[l e f t; r i g h t]$ [left; right] intervalında $f (x)$ -ın minimal olduğu $x$ qiymətini tapır. Başlanğıcda interval $[l e f t; r i g h t] = [1; n]$ [left; right] = [1; n] olar.

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$ və $r i g h t$ arasındakı fərq $3$ -dən böyük deyil. Bu halda $[l e f t; r i g h t]$ [left; right] intervalında $f (x)$ -ın minimal qiymətini tam iterasiya ilə tapırıq.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Binaları çeşidləyirik.

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

Cavabı hesablayırıq və çıxış edir. Binalar $1$ -dən $n$ -ə kimi nömrələnir.

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