Загрузка...

Помогите Феде сходить в кино с Ксюшей

  • Нормальная
  • Не решено

Пролог

Федя влюблен в Ксюшу и постоянно зовет ее погулять или в кино. Однако, у Феди большое горе - каждый раз, когда он зовет Ксюшу куда-то, она отказывается со словами:

Не сегодня, мне много задали в компьютерном кружке.

Но именно сегодня Федор решил взять судьбу за рога и решить все задания вместе с Ксюшей, чтобы побыстрей покушать заветное мороженое. Но на одном из заданий у него случился ступор.

Задание

Функция get_minimum_swaps принимает на вход массив уникальных целых чисел arr. Внутри функции разрешено переставлять 2 любых элемента местами произвольное количество раз.

Ребята отправятся есть мороженое ровно тогда, когда сумма всех arr[i] - arr[i-1] будет минимальной среди всех возможных.

Важно: При этом разность не может быть отрицательной.

В качестве результата необходимо вернуть минимальное число перестановок, которое нужно сделать, чтобы получить желаемый массив.

Пример

get_minimum_swaps([1, 4, 5, 2, 7]) # 2

Последовательность шагов:

[1, 2, 5, 4, 7] [1, 2, 4, 5, 7]

Пример

get_minimum_swaps([1, 5, 4, 2, 7]) # 1

Действие выполняется за 1 шаг:

[1, 2, 4, 5, 7]

Пример

get_minimum_swaps([1, 5, 4, 2, 7, 20, 40, 3, 0]) # 8

Последовательность действий:

[0, 5, 4, 2, 7, 20, 40, 3, 1] [0, 1, 4, 2, 7, 20, 40, 3, 5] [0, 1, 2, 4, 7, 20, 40, 3, 5] [0, 1, 2, 3, 7, 20, 40, 4, 5] [0, 1, 2, 3, 4, 20, 40, 7, 5] [0, 1, 2, 3, 4, 5, 40, 7, 20] [0, 1, 2, 3, 4, 5, 7, 40, 20] [0, 1, 2, 3, 4, 5, 7, 20, 40]
21 / 165