1639: Кількість вставок


Submit solution


Points:10
Time limit:1.0s
Memory limit:64M
Author:

Problem types

Сортування вставками - один з простих алгоритмів впорядкування одновимірних масивів. Основна ідея даного методу полягає в тому, що на першому кроці порівнюються другий та перший елемент вихідного масиву. Якщо порядок між ними, в залежності від типу сортування (за зростанням чи за спаданням) порушений, то перший елемент пересувається на одну позицію вправо. Тепер відсортований масив складається з двох елементів.

Продовжуючи ітераційний процес далі, беремо наступний (третій, четвертий і так далі) елемент і по черзі порівнюємо його, починаючи з кінця, з іншими елементами в уже відсортованому масиві. Якщо порядок між порівнюваними елементами порушений, то міняємо їх місцями, якщо ні, то вставка нового елемента закінчена і переходимо до наступної ітерації.

enter image description here

Напишіть програму, яка знайде кількість вставок, які неохідно зробити для сортування масиву A цілих чисел таким алгоритмом.

Формат вхідних даних

Перший рядок містить ціле число N (1 <= N <= 1001) - кількість елементів масиву.

Наступний рядок містить самі елементи масиву A, які розділяються пропуском. (-10000 <= A_i <= 10000)

Формат вихідних даних

Вивести мінімальну кількість вставок, які необхідно зробити для сортування масиву описаним алгоритмом.

Приклад вхідних даних

5
2 1 3 1 2

Приклад вихідних даних

4

Пояснення

2 1 3 1 2 - початковий масив

1 2 3 1 2 - 1 вставка

1 2 3 1 2 - 0 вставок

1 1 2 3 2 - 2 вставки

1 1 2 2 3 - 1 вставка

Всього 4 ітерації та зроблено 4 вставки


Comments

There are no comments at the moment.