Задание №168133: Задание 4

Задача 4. ВелоForces
Значение k может быть от 1 до n, т.к. слон Семён совершил хотя бы 1 заезд длиной 1 км, а всего
он совершил n заездов.
Можно перебрать значения k от 1 до n и для каждого k посчитать, сколько в данном массиве
чисел, которые не меньше k. Если это количество также не меньше k, то слон Семён достиг уровня

k или выше. Запомним наибольшее из таких подходящих k. Пример такого решения.
n = int (input ())
a = [ int (input ()) for i in range(n )]
ans = 0
for k in range(1 , n + 1):
cnt = 0
for val in a :
if val >= k :
cnt += 1

if cnt >= k :
ans = k
print ( ans )
Такое решение имеет сложность O(n2) и набирает 50 баллов.
Для полного решения заметим, что подсчитывать числа, которые не меньше определённого зна-
чения удобно, если отсортировать значения по неубыванию. Пусть массив отсортирован и индексы
элементов массива начинаются с нуля. Если нулевой элемент массива не меньше n, то все остальные
элементы массива тоже не меньше n и поэтому уровень слона Семёна будет равен n. Если это не
так, но значение элемента массива с индексом 1 не меньше n (cid:0) 1, то уровень слона Семёна будет
равен n (cid:0) 1. Если и это неверно, но при этом элемент массива с индексом 2 не меньше n (cid:0) 2, то

уровень слона Семёна будет n (cid:0) 2. То есть нам нужно найти такое минимальное k, что a[k]>=n−k,
тогда уровень слона Семёна будет n (cid:0) k.
Такое решение имеет сложность O(nlogn) (ввиду использования быстрой сортировки) и наби-
рает 100 баллов.
n = int (input ())
a = [ int (input ()) for i in range(n )]
a . sort ()
k = 0
while a [ k ] < n − k :
k += 1

print (n − k)