Треба вибрати два різні подарунки з найбільшою сумою, що не перевищує .
Перебір усіх пар коштував би \mathcal{O}(N^2), що при N = 10^5 надто повільно. Класичний спосіб — відсортувати ціни й скористатися методом двох вказівників.
Поставимо вказівник на початок відсортованого масиву, а — на кінець, і рухатимемо їх назустріч:
якщо a_l + a_r \le X, ця пара допустима — оновлюємо відповідь і зсуваємо праворуч, бо для поточного це вже найкращий можливий партнер;
якщо a_l + a_r > X, сума завелика, і зменшити її можна лише зсунувши ліворуч.
Цикл триває, доки l < r; умова l < r водночас гарантує, що подарунки різні.
Чому це коректно? На кожному кроці ми або фіксуємо найкращу пару для поточного , або доводимо, що поточне не входить у жодну допустиму пару з і більшими. Тому жодного оптимального варіанту не пропущено.
Альтернатива — для кожного a_i шукати двійковим пошуком найбільше a_j \le X - a_i з j \ne i; складність \mathcal{O}(N \log N), така ж, як і в сортування.
Ціни й сягають 10^9, тому суму рахуйте у 64-бітному типі. Якщо жодної допустимої пари немає, дійте за форматом умови.