Qatar çeşidləyicisi#8735

Qatar çeşidləyicisi (Həll təhlili)

Tutaq ki, $m$ massivinə giriş permutasiyası daxildir — vaqonların cari sırası. Axtarılan minimal permutasiya sayı bu permutasiyanın sərtliyinə bərabərdir.

İnversiya $(m_{i}, m_{j})$ (m_i, m_j) cütlükdür, belə ki, $i < j$ i < j, amma bu zaman $m_{i} > m_{j}$ m_i > m_j. Başqa sözlə desək, elementlər cütlüyü inversiya əmələ gətirir, əgər onlar qeyri-düzgün qaydada yerləşiblər.

Məsələn, $m = {3, 1, 2}$ m = \{3, 1, 2\} massivində $(3, 1)$ və $(3, 2)$ cütlükləri inversiya əmələ gətirir. $(1, 2)$ cütlüyü inversiya əmələ gətirmir, çünki 1 və 2 düzgün ardıcıllıqla yerləşiblər.

Uzunluğu $n$ olan massivdə inversiyaların sayını iki dövrə vasitəsilə hesablamaq mümkündür: $1 \leq i < j \leq n$ 1 \le i < j \le n olan bütün mümkün $(i, j)$ cütlüklərini nəzərdən keçiririk və əgər $m_{i} > m_{j}$ m_i > m_j olarsa, inversiyalar sayğacını 1 artırırıq.

Nümunə

Permutasiyadakı inversiyaların sayılmasının nümunəsini nəzərdən keçirək. Hər bir rəqəmin altına onun sağ tərəfində yerləşən elementlərlə birlikdə yaradılan inversiyaların sayını yazaq. Qoy $in v [i]$ $i < j$ i < j və $m [i] > m [j]$ m[i] > m[j] olan indekslərin sayını göstərsin.

Ümumi inversiya sayı $16$ -ya bərabərdir.

Tapşırıq

Aşağıdakı nümunə üçün həlli modelləşdirin.

Alqoritmin reallaşdırılması

$m$ massivini elan edək.

int m[100010];

$t es t s$ testlərini ardıcıl olaraq emal edirik.

scanf("%d", &tests);
while (tests--)
{

Vaqonların giriş sırasını $m$ massivinə oxuyuruq.

  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%d", &m[i]);

Qatarı sıraya salmaq üçün tələb olunan minimal permutasiya sayını $r es$ dəyişənində hesablayırıq.

  res = 0;
  for (i = 0; i < n - 1; i++)
  for (j = i + 1; j < n; j++)
    if (m[i] > m[j]) res++;

Cavabı çıxışa veririk.

  printf("Optimal train swapping takes %lld swaps.\n", res);
}