У Никиты есть n банок газировки разного объема. Он хочет найти k-ю по полезности банку, при этом следуя принципу пить

Murka

69

Для решения данной задачи без использования встроенных алгоритмов сортировки, мы можем использовать алгоритм сортировки вставками.

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

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

1. Элементы в новом списке будут расположены в порядке убывания их объемов.
2. Мы должны остановиться после добавления k-го элемента.

Для каждого элемента исходного списка, мы будем итерироваться по элементам нового списка и сравнивать объемы. Если объем элемента исходного списка больше или равен объему текущего элемента нового списка, мы вставляем его перед текущим элементом. Если объем элемента исходного списка меньше объема текущего элемента нового списка, мы продолжаем итерироваться по новому списку.

После того, как мы вставили все элементы исходного списка в новый список, просто выводим объем k-го элемента нового списка.

Вот реализация данного алгоритма на языке Python:

python

n, k = map(int, input().split())

volumes = list(map(int, input().split()))



sorted_volumes = []

for i in range(n):

    j = 0

    while j < len(sorted_volumes) and volumes[i] < sorted_volumes[j]:

        j += 1

    sorted_volumes.insert(j, volumes[i])

    if len(sorted_volumes) > k:

        sorted_volumes.pop()



print(sorted_volumes[k-1])

При вводе чисел 5 и 5, а также списка объемов [1, 7, 2, 3], данный код выведет число 3, что соответствует объему 5-ой по полезности банки.

Надеюсь, это решение понятно и полезно для вас. Если у вас возникнут дополнительные вопросы, пожалуйста, не стесняйтесь задавать их.