1. Идея

Нужно просто отсортировать все данные инвентарные номера по неубыванию и вывести их.

Так как повторения разрешены, одинаковые числа должны остаться в результате столько раз, сколько они встретились во входных данных.

2. Наблюдения

• От нас не требуется делать ничего сложнее обычной сортировки.
• Числа могут быть:
  • отрицательными,
  • положительными,
  • равными нулю,
  • большими по модулю.
• Но стандартная сортировка умеет корректно работать с такими значениями.
• Важно именно сохранить все элементы, а не только разные.

Например, если были числа 3 1 3 2, то после сортировки получим 1 2 3 3.

3. Алгоритм

1. Считать число n.
2. Считать массив из n целых чисел.
3. Отсортировать массив по возрастанию.
4. Вывести элементы массива через пробел.

4. Почему это работает

Стандартная сортировка переставляет элементы массива так, что для любых соседних элементов выполняется условие: левый не больше правого.

Именно это и означает порядок неубывания.

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

5. Сложность

Пусть n — количество книг.

• Считывание массива: O(n)
• Сортировка: O(n log n)
• Вывод ответа: O(n)

Итоговая сложность: O(n log n).

По памяти:

• хранение массива требует O(n).

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    for (int i = 0; i < n; i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << a[i];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))
a.sort()
print(*a)