11460. K-ый Гутаб

В ADA Университете продаются n видов гутабов. Гутаб i-го вида стоит ai гяпиков.

Гутаб — азербайджанское блюдо из тонко раскатанного теста, которое быстро готовят на выпуклой сковороде, известной как садж. Существует множество вариаций гутаба: обычно в качестве начинки используют тыкву и зелень. Есть также шамахинский гутаб, яшыл гутаб, карын гутаб, гузу гутаб, девэ гутаб – региональные разновидности, характерные для посёлка Джорат и других районов Азербайджана.

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

Найдите k-ю наименьшую возможную цену, которую Хусейн может заплатить. Если существует несколько наборов гутабов с одинаковой ценой, эта цена учитывается только один раз.

Вход. Первая строка содержит два целых числа: n (1 ≤ n ≤ 10) и k (1 ≤ k ≤ 2 ⋅ 10⁵). Вторая строка содержит n целых чисел – цены различных видов гутабов: a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Выход. Выведите k-ю наименьшую цену, которую может заплатить Хусейн.

Пример. Шесть наименьших цен, которые может заплатить Хусейн:

· 5 гяпиков

· 10 гяпиков

· 11 гяпиков

· 15 гяпиков

· 11 + 5 = 16 гяпиков

· 20 гяпиков

Таким образом, ответ 20.

Пример входа	Пример выхода
5 6 5 10 11 15 20	20

РЕШЕНИЕ

структуры данных – set

Анализ алгоритма

Добавим во множество число 0. Затем выполним k шагов:

· Найдём наименьший элемент множества x и удалим его.

· Для каждого i (1 ≤ i ≤ n) добавим во множество элемент x + a_i;

После выполнения k шагов наименьший элемент множества будет равен k-ой наименьшей цене, которую может заплатить Хусейн.

Реализация алгоритма

Читаем входные данные.

scanf("%d %d", &n, &k);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

Добавляем во множество s число 0.

s.insert(0);

Совершаем k итераций.

for (i = 0; i < k; i++)

{

Извлекаем и удаляем наименьший элемент x.

x = *s.begin(); s.erase(x);

Для каждого i (1 ≤ i ≤ n) добавляем во множество элемент x + a_i.

for (j = 0; j < n; j++)

s.insert(x + m[j]);

}

Выводим ответ: k-ую наименьшую цену, которая равна наименьшему элементу множества.

printf("%lld\n", *s.begin());

Python реализация - TLE

Функция min() работает за O(n), поскольку проходит по всем элементам множества, чтобы найти наименьший.

В Python множества являются неупорядоченными коллекциями, поэтому min() не может воспользоваться какой-либо внутренней упорядоченностью или структурой. Вместо этого она проверяет каждый элемент отдельно, чтобы определить минимум, что приводит к линейной временной сложности, пропорциональной числу элементов во множестве.

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

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

s = set({0})

for _ in range(k):

x = min(s)

s.remove(x)

for value in m:

s.add(x + value)

print(min(s))

Python реализация

SortedSet поддерживает элементы в отсортированном порядке, используя внутренний отсортированный список.

Доступ к элементу по индексу (например, s[0] для наименьшего элемента) выполняется за константное время, так как SortedSet напрямую извлекает элемент по указанному индексу без дополнительных вычислений.

Операция add() в SortedSet из библиотеки sortedcontainers выполняется за время O(log n), где n – количество элементов во множестве.

from sortedcontainers import SortedSet

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

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

s = SortedSet([0])

for _ in range(k):

x = s[0]

s.discard(x)

for value in m:

s.add(x + value)

print(s[0])