Kimsenin Kazanamayacağı Ödül#9878

Kimsenin Kazanamayacağı Ödül (Editoryal)

Ürünlerin fiyatlarını azalmayan sırada sıralayalım. Aksiyona $c_{1} \leq c_{2} \leq ... \leq c_{k}$ c_1 \le c_2 \le ... \le c_k fiyatlı ürünler katılsın. Alıcı için en kazançlısı bunların en pahalı ikisini — $c_{k - 1}$ c_{k−1} ve $c_{k}$ c_k — satın almaktır. Eğer $c_{k - 1} + c_{k} > x$ c_{k−1} + c_k > x ise, hediye olarak tek boynuzlu at boynuzu alacaktır.

$a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n — tüm $n$ ürünün sıralanmış fiyatları olsun. O zaman aksiyona $a_{1}, a_{2}, ..., a_{k}$ a_1, a_2, ..., a_k fiyatlı ürünler dahil edilmelidir, burada $k$ — $a_{k - 1} + a_{k} \leq x$ a_{k−1} + a_k \le x koşulunu sağlayan en büyük indekstir.

Örnek

Birinci örnekte sıralanmış fiyatlar: ${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 koşulunu sağlayan en büyük $k$ indeksini arıyoruz. Bu $k = 3$ k = 3'tür, çünkü $2 + 3 \leq 6$ 2 + 3 \le 6, ama $3 + 4 > 6$ 3 + 4 > 6.

İkinci örnekte sıralanmış fiyatlar: ${1, 4, 7, 8, 9}$ \{1, 4, 7, 8, 9\}. $x = 10$ x = 10 olduğundan, en büyük $k$ indeksi $2$ 'dir: $1 + 4 \leq 10$ 1 + 4 \le 10, ama $4 + 7 > 10$ 4 + 7 > 10.

Algoritmanın Gerçeklenmesi

Giriş verilerini okuyoruz.

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

Ürünlerin fiyatlarını azalmayan sırada sıralıyoruz.

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

$i$ ve $i + 1$ i + 1 komşu ürün çiftlerini geziyoruz. $v_{i} + v_{i + 1} > x$ v_i + v_{i+1} > x olur olmaz, $v_{i + 1}$ v_{i+1} fiyatlı ürün ve ondan sonraki tüm ürünler artık aksiyona dahil edilemez.

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

O zaman aksiyondaki maksimum ürün sayısı $i + 1$ i + 1'e eşittir (numaralandırma sıfırdan başlar).

    res = i + 1;
    break;
  }

Cevabı yazdırıyoruz.

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