Найбiльший периметр#88

Найбiльший периметр (Editorial)

Три відрізки утворюють трикутник тоді й лише тоді, коли найбільший з них менший за суму двох інших (нерівність трикутника). Якщо палички впорядковані за спаданням, достатньо перевірити одну нерівність замість трьох.

Відсортуємо масив за незростанням: a_1 \ge a_2 \ge \ldots \ge a_N. Тепер стверджуємо: якщо відповідь існує, то оптимальна трійка — це три сусідні палички у відсортованому порядку.

Чому? Нехай найдовша паличка трикутника — це . Тоді дві інші вигідно взяти якомога довшими, тобто a_{i+1} та a_{i+2}; будь-який інший вибір дає менший периметр і водночас ускладнює виконання нерівності. Тому перебираємо від до N-2 і беремо першу трійку, для якої

a_i < a_{i+1} + a_{i+2}.

Оскільки ми йдемо за спаданням, перша знайдена трійка одразу дає найбільший периметр — шукати далі не потрібно.

Якщо жодна трійка не підійшла, трикутник побудувати неможливо і треба вивести .

Складність — \mathcal{O}(N \log N) через сортування. Довжини сягають 10^9, тому суму двох паличок краще рахувати у 64-бітному типі.