Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
0 / 0 / 0
Регистрация: 05.10.2017
Сообщений: 1
1

Задача про сортировку слиянием

05.10.2017, 18:09. Просмотров 1743. Ответов 1
Метки нет (Все метки)

Помогите, пожалуйста! Изучаю алгоритмы программирования, сейчас на тема сортировки, конкретнее - сортировка слиянием.
Задача:
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Инверсией в последовательности чисел A называется такая ситуация, когда i<j, а Ai>Aj.

Дан массив целых чисел. Ваша задача — подсчитать число инверсий в нем.

Подсказка: чтобы сделать это быстрее, можно воспользоваться модификацией сортировки слиянием.

Формат входного файла
В первой строке входного файла содержится число n (1≤n≤10^5) — число элементов в массиве. Во второй строке находятся n целых чисел, по модулю не превосходящих 10^9.

Формат выходного файла
В выходной файл надо вывести число инверсий в массиве.
если сделать обычную сортировку слиянием, а потом считать число инверсий "в лоб" то будет time limit, т.к. в лоб считает за O(n^2).
Как модифицировать сортировку слиянием, или как впринцепе решить эту задачу?
Спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.10.2017, 18:09
Ответы с готовыми решениями:

Задача на пузырьковую сортировку
Представьте пузырьковую сортировку в которой элементы сравниваются не по очереди, а случайно...

Задача на случайную сортировку
Задача: Есть 8 команд по 10 человек. Каждая команда из разных городов. Нужно разделить людей так же...

Задача про матрицу и сортировку массива
Помогите пожалуйста решить задачу : Дана квадратная матрица. Получить одномерный массив...

Задача про сортировку массива и его вывод
Помогите пожалуйста решить задачку : Дана квадратная матрица 4х4. Сделать одномерный массив,...

1
Модератор
2740 / 1900 / 411
Регистрация: 26.03.2015
Сообщений: 7,065
05.10.2017, 21:59 2
В функции Слияние при добавлении в выходной массив элемента из второго массива увеличивайте количество инверсий на количество оставшихся в первом массиве элементов.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.10.2017, 21:59

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Самая простая задача на свете про сортировку
Супер простая задача на сортировку. Дается N чисел (N ≤ 10^6), которые по абсолютной величине не...

Сортировку вставками меняем на сортировку слиянием
Код программы выполняет сортировку массива вставками. Как сюда вставить код сортировки массива...

Задача про сортировку с использованием связного списка, нужно найти ошибку
Имеется файл состоящий из данных о студентах(ФИО, номер группы, средний бал). Построить...

Пояснить сортировку слиянием
Что выполняет???мне нужн ответ... +можете написать обозначение функции(если сможете) ( //-? )...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.