Дівчата та хлопці#35

Дівчата та хлопці (Editorial)

Розв'язок стане очевидним, якщо відсортувати складності за неспаданням.

Хлопцям дістаються задачі зі складністю d_i \le x, а дівчатам — з d_i > x. Тобто, хоч би яким був , хлопці завжди отримують деякий префікс відсортованого масиву. Щоб хлопцям дісталося рівно задач, цей префікс має мати довжину .

Позначимо відсортований масив d_1 \le d_2 \le \ldots \le d_n. Умова «перші задач у хлопців, решта в дівчат» рівносильна подвійній нерівності

d_b \le x < d_{b+1}.

Отже, підходять усі цілі з відрізка [d_b,\; d_{b+1} - 1], а їх рівно

d_{b+1} - d_b.

Якщо d_b = d_{b+1}, різниця дорівнює нулю — і це правильна відповідь: дві задачі однакової складності неможливо розділити між командами, тому жодне не підходить.

Оскільки a + b = n і 1 \le b < n, індекси та b+1 завжди коректні. Складність — \mathcal{O}(n \log n) через сортування.