K-cı Qutab (Həll təhlili)

Cəmiyətə $0$ ədədini əlavə edək. Sonra $k$ addım həyata keçirək:

• Cəmiyyətin ən kiçik elementi $x$-ı tapırıq və onu silirik.

• Hər bir i~(1 \le i \le n) üçün cəmiyyətə x + a_i ədədini əlavə edirik;

$k$ addımın icrasından sonra cəmiyyətin ən kiçik elementi Hüseynin ödəyə biləcəyi $k$-cı ən kiçik qiymət olacaq.

Alqoritmin icrası

Giriş verilənlərini oxuyuruq:

scanf("%d %d", &n, &k);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Cəmiyyətə $s$ ədədini $0$ ədədini əlavə edirik.

s.insert(0);

$k$ iterasiya həyata keçiririk.

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

Ən kiçik elementi $x$-ı çıxarıb və silirik.

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

Hər bir i~(1 \le i \le n) üçün cəmiyyətə x + a_i ədədini əlavə edirik.

  for (j = 0; j < n; j++)
    s.insert(x + m[j]);
}

Cəmiyyətin ən kiçik elementi olan $k$-cı ən kiçik qiyməti, yəni cavabı çıxarırıq.

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

Python realizasiyası — TLE

min() funksiyası $O(n)$ vaxtda işləyir, çünki cəmiyyətin bütün elementlərini yoxlayaraq ən kiçik olanını tapır.

Python-da cəmiyyətlər müəyyən sıra ilə təşkil olunmur, buna görə də min() funksiyası hər hansı daxili sıralama və ya strukturu istifadə edə bilmir. Bunun əvəzinə, hər elementi bir-bir yoxlayaraq minimumu müəyyən edir ki, bu da cəmiyyətin elementlərinin sayına mütənasib olaraq xətti vaxt mürəkkəbliyinə gətirir.

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 realizasiyası

SortedSet elementləri sıralı şəkildə saxlayır və bunun üçün daxili sıralı siyahıdan istifadə edir.

İndeks üzrə elementə daxil olmaq (məsələn, $s[0]$ ən kiçik element üçün) sabit zamanda baş verir, çünki SortedSet verilmiş indeksdən birbaşa elementi çıxarır əlavə hesablamaya ehtiyac olmadan.

sortedcontainers kitabxanasındakı SortedSet üçün add() əməliyyatı O(log n) vaxt sahəsinə malikdir, burada $n$ cəmiyyətdəki elementlərin sayıdır.

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])