|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
07.06.2015, 16:27 | #1 |
Новичок
Джуниор
Регистрация: 29.05.2015
Сообщений: 2
|
сортировка за O(n)
Карточки с числами ограничение по времени на тест1 секунда ограничение по памяти на тест256 мегабайт ввод input.txt вывод output.txt У Пети есть 2n карточек, на каждой из которых написано некоторое целое число. Числа на карточках могут совпадать. Пусть все карточки пронумерованы последовательными целыми числами от 1 до 2n. Число, записанное на карточке с номером i, обозначим как ai. Для того, чтобы сыграть с друзьями в одну увлекательную игру, Пете нужно разбить карточки на пары таким образом, чтобы в каждой паре числа на карточках были одинаковы. Помогите Пете это сделать. Входные данные В первой строке записано целое число n (1 ≤ n ≤ 3·105). Во второй строке записана последовательность из 2n положительных целых чисел a1, a2, ..., a2n (1 ≤ ai ≤ 5000) — числа, которые написаны на карточках. Числа в строке разделяются одиночными пробелами. Выходные данные Если невозможно разбить карточки на пары так, чтобы в каждой паре на карточках были написаны одинаковые числа, в единственной строке выведите число -1. Если же искомое разбиение существует, то выведите n пар чисел, по одной паре в строке — номера карточек, образующих пары. Числа в парах разделяйте пробелами. Пары и числа в парах можно выводить в любом порядке. Если решений несколько, выведите любое из них. |
07.06.2015, 17:28 | #2 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
В чем проблема?
Я бы создал массив p[1..5000], где p[i] есть список, содержащий номера карточек, значение которых равно i. Дальше все супер просто. Бежим по массиву и ищем список, кол-во элементов в котором нечетно. Если такой имеется, пишем -1. Коли нет, выводим попарно все элементы p[i], где i in [1..5000]. Всё |
07.06.2015, 19:03 | #3 |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
То, что Ромаха описал называется сортировкой подсчетом. Более подробно можно у Скиены, например прочитать в "Алгоритмы и структуры данных".
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Быстрая сортировка(сортировка Хоара). Сортировка фрагмента массива [C++] | druger | Помощь студентам | 0 | 20.04.2012 15:49 |
Сортировка Шелла и Шейкер-сортировка | AleksandrMakarov | Паскаль, Turbo Pascal, PascalABC.NET | 11 | 11.03.2012 12:18 |
Сортировка массива методами предсортировки и слияния, и пирамидальная сортировка. | lenny_24 | Помощь студентам | 2 | 17.04.2011 18:57 |
паскаль,одномерный массив,сортировка вставка,сортировка убывания,от максимального до конца | немозг | Помощь студентам | 11 | 06.02.2010 21:57 |
Сортировка файлов в Explorer vs сортировка в Delphi | mutabor | Общие вопросы Delphi | 11 | 04.09.2009 14:32 |