K-тий Гутаб#11460

K-тий Гутаб (Розбір)

Додамо в множину число $0$ . Потім виконаємо $k$ кроків:

Знайдемо найменший елемент множини $x$ і видалимо його.
Для кожного $i (1 \leq i \leq n)$ i~(1 \le i \le n) додамо до множини елемент $x + a_{i}$ 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 \leq i \leq n)$ i~(1 \le i \le n) додаємо до множини елемент $x + a_{i}$ 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

Python реалізація

SortedSet підтримує елементи у відсортованому порядку, використовуючи внутрішній відсортований список.

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

Операція add() у SortedSet з бібліотеки sortedcontainers виконується за час $O (l o g n)$ 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])

Python