Ən az artırmaq#9023

Ən az artırmaq (Həll təhlili)

Gəlin, minimum əməliyyat sayının başlanğıc massivini

m [0], m [1], ..., m [n - 1]

m[0], m[1], ..., m[n - 1]

növündəki arifmetik proqresiyaya çevirdiyini fərz edək

x, x + 1, x + 2, ..., x + n - 1

x, x + 1, x + 2, ..., x + n - 1

Açıq-aydın, $m [0] \leq x \leq ma x (m [0], m [1], ..., m [n - 1])$ m[0] \le x \le max(m[0], m[1], ..., m[n - 1]).

Biz sıralamanı

d = [x, x + 1, x + 2, ..., x + n - 1]

d = [x, x + 1, x + 2, ..., x + n - 1]

uyğun adlandırırıqsa, o zaman bu ardıcıllığın $d$ , yəni hər bir $i$ üçün $0$ -dən $n - 1$ n - 1-ə qədər $m [i] \leq d [i]$ m[i] \le d[i] şərtini yerinə yetirildiyi halda, massiv $m$ tarixə qədər $d$ ola bilər.

Uyğun olan ardıcıllığın $d$ olduğu minimum $x$ qiymətini müəyyən etmək lazımdır. Bunu binary axtarış üsulu ilə etmək olar.

Məsələnin nümunəsi

Gəlin ilk testi nəzərdən keçirək. Minimum elementlər məbləğinə uyğun ardıcıllığın $d = [x, x + 1, x + 2, ..., x + n - 1]$ d = [x, x + 1, x + 2, ..., x + n - 1] olması fərz edək.

Açıq-aydın, $m [0] = 3 \leq x \leq 11 = ma x (m [i])$ m[0] = 3 ≤ x ≤ 11 = max(m[i]).

İkilik axtarış ilə növü uyğun ardıcıllığın $d$ olması üçün minimum $x$ qiymətini öyrənirik.

Məsələn, $x = 6$ x = 6 olaraq ardıcıllığın $d$ uyğun olmayacaq, amma $x = 8$ x = 8 isə uyğun olacaqdır.

İkinci testi nəzərdən keçirmək istəyirik. İkili axtarışı da $4 \leq x \leq 7$ 4 \le x \le 7 aralığında başlatırıq. Məsələn, artıq $x = 4$ x = 4 zamanı ardıcıllıq $d$ uyğun olur.

Alqoritmin tətbiqi

Giriş ardıcıllığını $m$ massivində saxlayırıq. Arifmetik proqresiyanın ardıcıllığını, $x, x + 1, x + 2, ..., x + n - 1$ x, x + 1, x + 2, ..., x + n - 1 formatında, $d$ massivində saxlayırıq.

#define MAX 1000000
int m[MAX], d[MAX];

Yoxla funksiyası $d$ massivində növünə görə ardıcıllığı yaratır

f i r s t, f i r s t + 1, f i r s t + 2, ..., f i r s t + n - 1

first, first + 1, first + 2, ..., first + n - 1

Əgər hər bir $i (0 \leq i \leq n - 1)$ i~(0 \le i \le n - 1) üçün $m [i] \leq d [i]$ m[i] \le d[i] qeyri-bərabərliyi öyrənilirsə, $d$ sırası $m$ ardıcıllığından alınacaq, yəni ayrı-ayrı elementlərin $1$ artırılması yolu ilə. Bu halda $d$ sırası uyğun adlanır.

Əgər $d$ sırası uyğun olsa, Yoxla funksiyası $1$ qaytarır, əks halda — $0$ .

int check(int first)
{
  for (int i = 0; i < n; i++)
    d[i] = first++;
  for (int i = 0; i < n; i++)
    if (m[i] > d[i]) return 0;
  return 1;
}

C++

Proqramın əsas hissəsi. Giriş mənimliyinə $n$ oxuyuruq. $m$ massivində maksimum qiyməti $m x$ hesablayırıq.

scanf("%d", &n);
mx = 0;
for (i = 0; i < n; i++)
{
  scanf("%d", &m[i]);
  if (m[i] > mx) mx = m[i];
}

start = m[0];
end = mx;

C++

İkili axtarışı $x$ qiymətində $[s t a r t; e n d] = [m [0]; m x]$ [start; end] = [m[0]; mx] aralığında başlatırıq.

Minimum $x$ qiymətini tapırıq ki, $x, x + 1, x + 2, ..., x + n - 1$ x, x + 1, x + 2, ..., x + n - 1 ardıcıllığını əldə etmək mümkün olsun $m [0], m [1], ..., m [n - 1]$ m[0], m[1], ..., m[n - 1] massivindən.

while (start < end)
{
  mid = (start + end) / 2;
  if (check(mid))
    end = mid;
  else
    start = mid + 1;
}

C++

Əldə etmək istədiyimiz arifmetik proqresiyanı yaradırıq.

for (i = 0; i < n; i++)
  d[i] = start++;

Minimum əməliyyat sayı hesablanır ki, proqresiyanı əldə etmək mümükün olsun.

op = 0;
for (int i = 0; i < n; i++)
  op += (d[i] - m[i]);

Nəticəni çıxarırıq.

printf("%lld\n", op);