Главная
Библиотека
Программирование
Дан массив a1, . . . , an, где каждое число в массиве представляет собой вид защиты определенного компонента системы. Уров...

Дан массив a1, . . . , an, где каждое число в массиве представляет собой вид защиты определенного компонента системы. Уровень защиты системы равен MEX всех компонентов системы. MEX — это минимальное целое неотрицательное число, отсутствующее в массиве.

«Дан массив a1, . . . , an, где каждое число в массиве представляет собой вид защиты определенного компонента системы. Уровень защиты системы равен MEX всех компонентов системы. MEX — это минимальное целое неотрицательное число, отсутствующее в массиве.»

1 октября 2025
Программирование

Условие:

Напиши программу на языке С++ 17, которая решала бы следующую задачу:

Вы — специалист по кибербезопасности в крупной компании. Ваша задача — проанализировать систему на наличие уязвимостей.
Вам дан массив a1, . . . , an, где каждое число в массиве представляет собой вид защиты определенного компонента системы.
Как известно, уровень защиты системы равен MEX всех компонентов системы. MEX — это минимальное целое неотрицательное число, отсутствующее в массиве. Например, MEX({1,2,3})=0, а MEX({0,2,1,4})=3.
Вы можете изменить любое значение массива a на любое другое целое число. Ваша задача — для каждого целого числа x от 0 до n посчитать минимальное необходимое количество изменений, чтобы MEX массива стал равен в точности x.

Формат входных данных
Первая строка содержит единственное число n (1<=n<=2*10^5) — размер массива.
Вторая строка содержит n целых чисел a1, . . . , an (0<=ai<=n).

Формат выходных данных
Для каждого x от 0 до n выведите в отдельной строке минимальное количество изменений в массиве a, чтобы MEX его элементов стал равен в точности x.

ограничение по времени 2 секунды
ограничение памяти 256 МБ

Решение:

Для решения данной задачи на языке C++ 17, мы можем использовать следующий подход: 1. Сначала мы создадим массив, который будет хранить количество вхождений каждого числа от 0 до n в нашем массиве. 2. Затем мы будем итерироваться по всем возможным значениям MEX от 0 до n и вычислять, сколько изменений нам нужно сделать, чтобы MEX стал равен текущему значению. 3. Для каждого значения x мы будем проверять, присутствует ли оно в массиве и сколько элементов меньше x, чтобы определить, сколько изменений необходимо. Теперь давайте напишем программу, следуя этому алгоритму. ```cpp #include iostrea...