Разбор: Игровая арифметика

$n$ — размер массива $a$

$a$ — массив чисел

Это игра минимакс: Алиса хочет минимизировать конечный счет, Боб хочет максимизировать его. Оба играют оптимально, и Алиса ходит первой.

Напомним, что арифметическое среднее использует целочисленное деление: $\lfloor S / n \rfloor$.

Подзадача 1: $n = 3$ ($20$ баллов)

С только $3$ элементами Алиса удаляет один, а Боб удаляет другой, оставляя один элемент в качестве конечного счета. У Алисы всего $3$ варианта выбора и $2$ оставшихся варианта для Боба — мы можем проверить все $6$ возможностей с помощью условных операторов.

Временная сложность: $O(1)$
Пространственная сложность: $O(1)$

Подзадача 2: Все $a_i$ одинаковы ($15$ баллов)

Если все значения равны некоторой константе $c$, то арифметическое среднее равно $\lfloor nc / n \rfloor = c$ до удаления и $\lfloor (n-2)c / (n-2) \rfloor = c$ после удаления. Счет никогда не меняется, поэтому ответ всегда .

Временная сложность: $O(n)$
Пространственная сложность: $O(n)$

Подзадача 3: $n \leq 10^3$ ($25$ баллов)

Мы перебираем минимакс. Для каждого возможного выбора $a_i$, который Алиса может удалить, мы моделируем оптимальный ответ Боба: Боб выберет элемент $a_j$ ($j \neq i$), который максимизирует конечный счет . Это означает, что Боб удалит наименьший оставшийся элемент (так как удаление меньшего значения сохраняет сумму больше).

Для каждого выбора Алисы $a_i$ мы вычисляем, что лучшее может достичь Боб. Алиса выберет $a_i$, который минимизирует это значение. Затем мы сравниваем результат с начальным счетом.

Временная сложность: $O(n^2)$
Пространственная сложность: $O(n)$

Подзадача 4: Полное решение ($40$ баллов)

Алиса хочет максимально уменьшить конечный счет, поэтому ее оптимальная стратегия — удалить наибольший элемент — это максимально уменьшает сумму. Боб хочет сохранить конечный счет как можно выше, поэтому его оптимальная стратегия — удалить наименьший оставшийся элемент — это максимально сохраняет сумму.

Алгоритм:

1. Отсортируйте массив $a$.
2. Вычислите начальный счет: $\text{initial} = \lfloor S / n \rfloor$, где $S = \sum a_i$.
3. Удалите $a[n-$ (наибольший, выбор Алисы) и (наименьший, выбор Боба).

Временная сложность: $O(n)$
Пространственная сложность: $O(n)$

Код решения