Условие
В ряд стоят N звуковых мониторов. Их исходные громкости уже упорядочены: a₁ ≤ a₂ ≤ … ≤ aₙ. N чётно. За действие можно выбрать ровно N/2 подряд идущих мониторов и увеличить громкость каждого на 1. Разрешено не более K действий. Найдите наибольшую достижимую минимальную громкость среди всех мониторов.
Входные данные
В первой строке N, во второй K, затем N чисел aᵢ, каждое на отдельной строке. 2 ≤ N ≤ 10^5, N чётно; 1 ≤ K ≤ 10^9; 1 ≤ aᵢ ≤ 10^9; a₁ ≤ … ≤ aₙ.
Что вывести
Выведите одно целое число — ответ на задачу.
Как понимать условие
Звуковой монитор здесь — колонка на сцене; aᵢ задаёт её громкость. За одно действие увеличивается громкость сразу у половины всех колонок, причём выбранные колонки должны стоять подряд. Для [1, 2, 4, 5] и K = 3 можно трижды выбрать первые две колонки: получится [4, 5, 4, 5]. Самая тихая теперь имеет громкость 4 — это и нужно вывести. Исходный порядок уже отсортирован, переставлять колонки во время решения нельзя.
Два монитора, которые нельзя поднять вместе
Обозначим h = N/2. Рассмотрим первый монитор и монитор с номером h + 1. Между ними h позиций, поэтому ни один отрезок длины h не содержит оба. Если нужно достичь уровня T, первому требуется max(0, T − a₁) действий, второму — max(0, T − aₕ₊₁).
Эти действия различны. Необходимое условие: max(0, T − a₁) + max(0, T − aₕ₊₁) ≤ K. Например, для [1, 2, 4, 5] и T = 4 нужны как минимум три действия.
Проверьте рассуждение
В массиве [1, 2, 4, 5] одно действие затрагивает два соседних элемента. Можно ли одним действием увеличить первый и третий?
Почему этой проверки достаточно
Выполним max(0, T − a₁) прибавлений на первой половине массива и max(0, T − aₕ₊₁) — на второй. В каждой половине все исходные значения не меньше её первого элемента: массив отсортирован. Значит, каждый монитор достигнет T.
Необходимое условие оказалось достаточным. Смещать отрезки между половинами не требуется. После действий массив может перестать быть отсортированным; доказательство использует только исходный порядок.
Формула вместо бинарного поиска
Пусть A = a₁, B = aₕ₊₁; A ≤ B. При T ≤ B действия нужны только первой половине, и T ≤ A + K. При T > B требуется 2T − A − B действий, поэтому T ≤ (A + B + K) // 2.
Обе границы вместе дают ответ min(A + K, (A + B + K) // 2). Если A + K ≤ B, первая граница достижима. Иначе достижима вторая: до B первая половина требует B − A действий, а оставшиеся действия распределяются между половинами. Время с чтением — O(N), вычисление ответа — O(1).
Где ломается правдоподобная идея
Нельзя прибавить K к минимуму и остановиться: для [1, 1] и K = 1 ответ остаётся 1. Также нельзя использовать только общий прирост суммы: первый элемент может ограничивать результат раньше среднего.
При N = 2 выбирается ровно один монитор. В Python при нумерации с нуля второй нужный элемент — a[n // 2]. В приведённом коде память O(N) из-за хранения массива; при последовательном чтении C++ можно оставить только два значения.
Реализация на Python
n = int(input())
k = int(input())
a = [int(input()) for _ in range(n)]
first = a[0]
second = a[n // 2]
print(min(first + k, (first + second + k) // 2))
Реализация на C++17
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; long long k; cin >> n >> k;
vector<long long> a(n); for (auto &x:a) cin >> x;
cout << min(a[0]+k, (a[0]+a[n/2]+k)/2) << "\n";
}