Сортувальник поїзда#8735

Сортувальник поїзда (Розбір)

Нехай масив $m$ містить вхідну перестановку — поточний порядок вагонів. Потрібна мінімальна кількість перестановок дорівнює числу інверсій у цій перестановці.

Інверсією називається така пара елементів $(m_{i}, m_{j})$ (m_i, m_j), що $i < j$ i < j, але при цьому $m_{i} > m_{j}$ m_i > m_j. Іншими словами, пара елементів утворює інверсію, якщо вони розташовані у неправильному порядку.

Наприклад, у масиві $m = {3, 1, 2}$ m = \{3, 1, 2\} інверсії утворюють пари $(3, 1)$ та $(3, 2)$ . Пара $(1, 2)$ інверсії не утворює, оскільки числа $1$ і $2$ розташовані відносно одне одного у правильному порядку.

Кількість інверсій у масиві довжини $n$ можна порахувати за допомогою подвійного циклу: переберемо всі можливі пари $(i, j)$ , для яких $1 \leq i < j \leq n$ 1 \le i < j \le n, і якщо $m_{i} > m_{j}$ m_i > m_j, збільшимо лічильник інверсій на одиницю.

Приклад

Розглянемо приклад підрахунку інверсій у перестановці. Під кожним числом запишемо кількість інверсій, які воно утворює з елементами, що стоять правіше нього. Нехай $in v [i]$ означає кількість таких індексів $j$ , для яких $i < j$ i < j і $m [i] > m [j]$ m[i] > m[j].

Загальна кількість інверсій дорівнює $16$ .

Вправа

Промоделюйте рішення для наступного прикладу.

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

Оголосимо масив $m$ .

int m[100010];

Послідовно обробляємо $t es t s$ тестів.

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

Вхідний порядок вагонів читаємо у масив $m$ .

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

Мінімальну кількість перестановок, необхідних для упорядкування поїзда, підраховуємо у змінній $r es$ .

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

Виводимо відповідь.

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