Автор, розробник, автор розбору: Тимур Дегтеарі
Ключове розуміння полягає в переформулюванні умов виграшу в термінах масивів різниць, а потім спостереженні, що оптимальний вибір трас відповідає префіксам відсортованих масивів.
Визначимо два допоміжні масиви:
c_i = e_i - s_i (позитивний, коли STI Guy швидший на трасі )
d_i = s_i - e_i (позитивний, коли EVO Guy швидший на трасі )
Нехай c' буде масивом , відсортованим у невисхідному порядку, а d' буде масивом , відсортованим у невисхідному порядку.
Оптимальний вибір трас для EVO Guy, щоб виграти, складається з префікса c'. Аналогічно, оптимальний вибір для STI Guy, щоб виграти, складається з префікса d'.
Для того, щоб EVO Guy виграв, нам потрібно: [_трасу i обрано c_i < 0]
Припустимо, що — найбільша підмножина трас, така що \sum_{c_i \in S} c_i < 0, і не відповідає префіксу c'. Оскільки c' відсортований у невисхідному порядку, заміна на префікс c' такої ж величини дасть суму, яка не перевищує початкову суму. Отже, префікс принаймні такий же хороший, як (і часто кращий за) будь-яку іншу підмножину такої ж величини.
За симетричним аргументом, те ж саме стосується перемоги STI Guy, використовуючи масив d'.
Обчисліть масиви і з вхідних даних.
Відсортуйте обидва масиви у невисхідному порядку.
Для кожного масиву знайдіть довжину найдовшого префікса, сума якого строго менша за .
Ці довжини дають R_E (для EVO Guy, використовуючи масив c') і R_S (для STI Guy, використовуючи масив d').
Примітка: Якщо жоден префікс не має негативної суми, відповідь дорівнює , що означає, що гонщик не може виграти незалежно від вибору трас.
Часова складність: O(n \log n) через сортування. Обчислення префіксної суми — .