Heç kimin qazana bilmədiyi mükafat#9878

Heç kimin qazana bilmədiyi mükafat (Həll təhlili)

Malların qiymətlərini azalmayan ardıcıllıqla sıralayaq. Tutaq ki, aksiyada $c_{1} \leq c_{2} \leq ... \leq c_{k}$ c_1 \le c_2 \le ... \le c_k qiymətlərinə malik mallar iştirak edir. Alıcı üçün onlardan ən bahalı ikisini — $c_{k - 1}$ c_{k−1} və $c_{k}$ c_k — almaq ən sərfəlisidir. Əgər $c_{k - 1} + c_{k} > x$ c_{k−1} + c_k > x olarsa, o, bircorn buynuzunu hədiyyə olaraq alacaq.

Tutaq ki, $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n — bütün $n$ malın sıralanmış qiymətləridir. Onda aksiyaya $a_{1}, a_{2}, ..., a_{k}$ a_1, a_2, ..., a_k qiymətlərinə malik mallar daxil edilməlidir, burada $k$ — $a_{k - 1} + a_{k} \leq x$ a_{k−1} + a_k \le x şərtini ödəyən ən böyük indeksdir.

Misal

Birinci misalda sıralanmış qiymətlər: ${1, 2, 3, 4, 5}$ \{1, 2, 3, 4, 5\}. $x = 6$ x = 6 olduğundan, $a_{k - 1} + a_{k} \leq 6$ a_{k−1} + a_k \le 6 şərtini ödəyən ən böyük $k$ indeksini axtarırıq. Bu $k = 3$ k = 3-dür, çünki $2 + 3 \leq 6$ 2 + 3 ≤ 6, lakin $3 + 4 > 6$ 3 + 4 > 6.

İkinci misalda sıralanmış qiymətlər: ${1, 4, 7, 8, 9}$ \{1, 4, 7, 8, 9\}. $x = 10$ x = 10 olduğundan, ən böyük $k$ indeksi $2$ -yə bərabərdir: $1 + 4 \leq 10$ 1 + 4 \le 10, lakin $4 + 7 > 10$ 4 + 7 > 10.

Alqoritmin reallaşdırılması

Giriş məlumatlarını oxuyuruq.

scanf("%d %d", &n, &x);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Malların qiymətlərini azalmayan ardıcıllıqla sıralayırıq.

sort(v.begin(), v.end());

$i$ və $i + 1$ i + 1 qonşu malların cütlərini nəzərdən keçiririk. $v_{i} + v_{i + 1} > x$ v_i + v_{i+1} > x olan kimi, $v_{i + 1}$ v_{i+1} qiymətinə malik mal və ondan sonrakı bütün mallar artıq aksiyaya daxil edilə bilməz.

res = n;
for (i = 0; i + 1 < n; i++)
  if (v[i] + v[i + 1] > x)
  {

Onda aksiyadakı malların maksimum sayı $i + 1$ i + 1-ə bərabərdir (nömrələmə sıfırdan başlayır).

    res = i + 1;
    break;
  }

Cavabı çap edirik.

printf("%d\n", res);