Разбор задачи: Maximum Median

Идея задачи

Дан массив из n элементов (гарантируется, что n нечётно). За одну операцию можно увеличить любой элемент массива на 1. Разрешено выполнить не более k операций.

Нужно максимизировать медиану массива.

Ключевые наблюдения

1. Сортировка

Медиана определяется в отсортированном массиве, поэтому первым делом отсортируем массив.

Пусть:

mid = n // 2

Тогда медиана — это a[mid].

2. Какие элементы имеет смысл увеличивать?

Важно: увеличивать элементы левее медианы бессмысленно.

Почему?

• Медиана зависит только от правой половины массива.
• Даже если увеличить маленькие элементы слева, они не повлияют на позицию медианы.

Значит, работаем только с отрезком [mid, n-1].

3. Основная стратегия

Будем постепенно «подтягивать» медиану вверх.

Идея:

• сначала поднимаем a[mid] до a[mid+1]
• затем уже два элемента до a[mid+2]
• затем три элемента и так далее

То есть мы поддерживаем группу элементов, которые уже выровнены.

Как это работает

Обозначим:

• cur — текущее значение медианы
• cnt — сколько элементов уже «на уровне» cur

На каждом шаге:

diff = a[i] - cur
need = diff * cnt

• diff — сколько нужно прибавить
• need — сколько операций нужно

Два случая

Хватает операций

Если k >= need, то:

• тратим need
• поднимаем уровень до a[i]
• увеличиваем cnt

Не хватает операций

Тогда мы уже не можем дойти до следующего уровня.

Просто равномерно распределяем оставшиеся операции:

cur += k // cnt

После цикла

Если дошли до конца массива, но операции остались:

cur += k // cnt

Почему это оптимально

Мы всегда:

• поднимаем минимально возможные элементы справа
• делаем это равномерно

Это минимизирует стоимость увеличения медианы.

Любая другая стратегия будет либо дороже, либо не даст лучшего результата.

Сложность

• Сортировка: O(n log n)
• Основной проход: O(n)

Итого:

O(n log n)

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());

    int mid = n / 2;
    long long cur = a[mid];
    long long cnt = 1;

    for (int i = mid + 1; i < n; i++) {
        long long diff = a[i] - cur;
        long long need = diff * cnt;

        if (k >= need) {
            k -= need;
            cur = a[i];
            cnt++;
        } else {
            cur += k / cnt;
            cout << cur << '\n';
            return 0;
        }
    }

    cur += k / cnt;
    cout << cur << '\n';

    return 0;
}

Реализация на Python

n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

mid = n // 2
cur = a[mid]
cnt = 1

for i in range(mid + 1, n):
    diff = a[i] - cur
    need = diff * cnt

    if k >= need:
        k -= need
        cur = a[i]
        cnt += 1
    else:
        cur += k // cnt
        print(cur)
        exit()

cur += k // cnt
print(cur)

Типичные ошибки

1. • Увеличение элементов слева от медианы
2. • Попытка делать бинарный поиск без аккуратной проверки
3. • Переполнение diff * cnt (нужно long long)
4. • Забывают, что n нечётно

Альтернативное решение (Binary Search)

Можно искать ответ бинарным поиском:

• проверяем, можно ли сделать медиану ≥ x
• считаем, сколько нужно операций

Но greedy-решение выше проще и быстрее реализуется.

Итог

• Сортируем массив
• Работаем только с правой половиной
• Поднимаем медиану «уровнями»
• Когда операций не хватает — делим остаток

Это классическая greedy-задача на медиану.