На c++

Задача понятна: есть n офисов с заданной высотой(a1…an). За один заказ можно увеличить или уменьшить высоту любого офиса на 1 этаж. Всего есть k заказов. Нужно минимизировать разницу между самым высоким и самым низким офисом после выполнения не более k заказов.

Подход (пошагово, понятно для школьников):

• Сначала отсортируем массив высот. Тогда изначальный минимум будет в начале, максимум — в конце.
• Будем работать «с краёв»: поднимем минимальные высоты или опустим максимальные, чтобы сузить диапазон.
• Пусть текущие минимальная высота L и максимальная R. Посчитаем:
  • cntL — сколько офисов на минимальном уровне L (количество элементов равных L в левом краю).
  • cntR — сколько офисов на максимальном уровне R (количество элементов равных R в правом краю).
• Сравниваем cntL и cntR:
  • Если cntL ≤ cntR, выгоднее поднимать все офисы на уровне L до следующего различия. Следующий уровень — следующая за L высота в массиве. Стоимость такого подъёма: deltaL * cntL, где deltaL — разница между следующей высотой и текущей L.
  • Иначе выгоднее опускать все офисы на уровне R до предыдущего различия. Стоимость: deltaR * cntR, где deltaR — разница между текущей R и предыдущей высотой.
• Если стоимость полностью помещается в оставшиеся k заказов, обновляем L или R соответственно и повторяем процесс (переходим к следующей группе одинаковых высот).
• Если же затрат слишком много, используем остаток k: поднимаем L на floor(k / cntL) или опускаем R на floor(k / cntR), и выходим.
• Итоговая разница: max(0, R - L).

Сложность: сортировка O(n log n) и один проход сдвигающихся границ — O(n). Используются long long для больших чисел.

Пример кода на C++ (совместим с компиляторами с C++17 и выше):

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, k;
    if (!(cin >> n >> k)) return 0;
    vector<long long> a(n);
    for (long long i = 0; i < n; ++i) cin >> a[i];

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

    long long i = 0;           // левая граница (индекс текущего минимального блока)
    long long j = n - 1;       // правая граница (индекс текущего максимального блока)
    long long L = a[i], R = a[j];

    while (L < R && k > 0) {
        // посчитаем количество элементов на минимальном уровне L
        long long i2 = i;
        while (i2 <= j && a[i2] == L) ++i2;
        long long cntL = i2 - i; // сколько элементов имеют высоту L

        // посчитаем количество элементов на максимальном уровне R
        long long j2 = j;
        while (j2 >= i && a[j2] == R) --j2;
        long long cntR = j - j2; // сколько элементов имеют высоту R

        if (cntL <= cntR) {
            // поднимаем левый блок до следующего distinto уровня
            if (i2 > j) break; // все элементы уже учтены, выход
            long long nextL = a[i2];
            long long delta = nextL - L;
            long long cost = delta * cntL;
            if (cost <= k) {
                k -= cost;
                i = i2;
                L = nextL;
            } else {
                long long inc = k / cntL;
                L += inc;
                k -= inc * cntL;
                break;
            }
        } else {
            // опускаем правый блок до предыдущего distinto уровня
            if (j2 < i) break; // все элементы уже учтены, выход
            long long prevR = a[j2];
            long long delta = R - prevR;
            long long cost = delta * cntR;
            if (cost <= k) {
                k -= cost;
                j = j2;
                R = prevR;
            } else {
                long long dec = k / cntR;
                R -= dec;
                k -= dec * cntR;
                break;
            }
        }
    }

    long long answer = (R > L) ? (R - L) : 0;
    cout << answer << "\n";

    return 0;
}

Пояснения по коду:

• Сортировка нужна, чтобы сгруппировать одинаковые высоты в начале и в конце.
• i и j — индексы границ текущего диапазона. L и R — текущие минимальная и максимальная высоты внутри этого диапазона.
• В каждом шаге считаются cntL и cntR — сколько офисов имеют минимальную и максимальную высоты на текущем крае.
• В зависимости от того, какая сторона “массивнее”, выбирается более выгодная цель поднимать/опускать. Если хватает бюджета, переходим к следующей границе; иначе делаем максимально возможное шаговое изменение и выходим.

Примечания и варианты:

• Если k достаточно большой, можно полностью выровнять все высоты, и разница станет 0.
• Альтернативный подход: бинарный поиск разности D и проверка минимального количества операций, чтобы привести все высоты в интервал длиной D. Теперь же двигаемся «по краям» и получаем линейную по времени реализацию после сортировки.

Если хочешь, могу привести тесты на нескольких примерах или разобрать конкретный набор данных из твоего примера.