Задача 28: Массивище
М. Густокашин
Во входном файле,
через пробел даны числа A1, A2 ... An. Отсортировать эти числа по
неубыванию и вывести отсортированный массив в выходной файл.
Входные данные
В первой строке входного файла дано число n (1<=n<=200000). Во
второй строке через пробел записаны числа A1, A2 ... An (-15000<=A<=15000).
Выходные данные
В единственной строке выходного файла должен быть
отсортированный массив.
Пример входного файла
4
4 3 1 2
Пример выходного файла
1 2 3 4
Решение:
Это первая разобранная на сайте задача, условие которой я придумал
сам! Итак, никакими стандартными средствами нам этот массив
отсортировать не удастся. Сортировка слиянием, использование
динамической памяти тоже не помогут (хотя кто их знает - сам не
пробовал).
Идея состоит в том, что необходимо создать массив из элементов word
размерностью от -15000 до 15000, изначально инициализированный
нулями. При появлении очередного числа увеличиваем элемент массива с
номером, равным этому числу на 1. При выводе просто проходим массив
от -15000 до 15000 и выводим число, равное номеру массива столько
раз, какое значение храниться в элементе с этим номером.
В этом решении есть ошибка. То есть не то что ошибка, а недоделка. А
что если какое то число встречается больше 65537 раз. Тогда
произойдет переполнение переменной word и восстановить массив станет
невозможно! Чтобы избавиться от этой проблемы надо завести массив из
3 элементов integer, в которых будут храниться указатели на
переполнившейся элемент массива. Переделать вывод результатов с
использованием этого массива - задача несложная, поэтому здесь
рассматриваться не будет ;)
Далее
ð
