Колобок ушёл от бабушки и поехал путешествовать. Неожиданно для себя он забрёл в страну…
- User
Колобок ушёл от бабушки и поехал путешествовать. Неожиданно для себя он забрёл в страну Ивэнлэнд. Первые трудности встали на его пути: Колобка и вход в страну отделял огромный ров с водой, которая, как известно, не очень хорошо влияет на нашего героя. К счастью, повсюду расположены воздушные потоки, которые могли поднимать того, кто на них встает, на определённую высоту. Страна не просто так названа Ивэнлэнд, поэтому все высоты, на которые могут поднять героя воздушные потоки "— это чётные числа.
Представим воздушные потоки как массив h[1..n] из n натуральных чисел — высот потоков. Для каждого 1≤i≤n посчитаем G[i] — индекс ближайшего элемента слева, строго большего h[i]. Более формально, G[i]=max{j|j<i и h[j]>h[i]}. Если i=1 или до h[i] нет ни одного элемента больше него, то G[i] считается равным 0
.
Колобок считает, что оптимальность расположения воздушных потоков определяется суммой S(h)=n∑i=1(i−G[i]). Чем меньше сумма, тем расположение оптимальнее. Всё, что может сейчас сделать Колобок — это увеличить высоту одного из воздушных потоков не более чем на m
. После этого действия высота потока должна остаться целым числом, но может, если необходимо, стать и нечётной.
Помогите Колобку сделать оптимальное изменение, которое позволит добиться, чтобы сумма S(h)
, описанная выше, после проделанного действия была минимальна. Формат входных данных
В первой строке входного файла даны числа n , m (1≤n≤105, 1≤m≤109
) — количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них.
Во второй строке даны высоты воздушных потоков h[i] (1≤h[i]≤109
). Гарантируется, что все высоты — чётные числа. Формат выходных данных
В единственной строке выходного файла выведите одно целое число — минимальную искомую сумму. Примеры Входные данные
3 100 4 2 6
Выходные данные
4
Входные данные
3 2 4 2 6
Выходные данные
5
Входные данные
3 10 2 2 2
Выходные данные
4
Примечания
В первом примере Колобку выгодно, например, увеличить первый элемент массива на 3, сделав его равным 7.
Тогда h=[7,2,6] , G[1]=0, G[2]=1 и G[3]=1, сумма S(h)=(1−0)+(2−1)+(3−1)=1+1+2=4. Добиться значения S(h)<4
невозможно.
Во втором примере m=2 и увеличить первый элемент так сильно не получится. После любого действия Колобка S(h) будет равно 5 или 6, пример действия, которое приводит к значению 5 "— увеличить первый элемент на 1, получив массив [5,2,6]
. Оценивание
Первая группа состоит из тестов, для которых выполняются ограничения 1≤n≤200 , m=109 и hi≤10 для всех i. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 19
баллов.
Вторая группа состоит из тестов, для которых выполняется ограничение 1≤n≤50 и m=109. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 18
баллов.
Третья группа состоит из тестов, для которых выполняется ограничение 1≤n≤2000 и m=109. Баллы за эту группу начисляются только при прохождении всех тестов группы и предыдущих групп. Стоимость группы составляет 23
балла.
Четвертая группа состоит из тестов, для которых выполняется ограничение 1≤n≤105 и m=109. Баллы за эту группу начисляются только при прохождении всех тестов группы и предыдущих групп. Стоимость группы составляет 21
балл.
Пятая группа состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов группы и предыдущих групп. Стоимость группы составляет 19 баллов.
реализуй следующее решение на C++, именно когда начинается часть для решения на 100 баллов: Дан массив высот h, каждый элемент массива — четное число; Для каждого его элемента hi посчитали G[i] = max{j | j < i и h[j] > h[i]}; Ввели функцию S(h) = Pn i=1 (i − G[i]); Разрешается увеличить один из элементов массива, требуется минимизировать S(h).
Научимся считать G за O(nlogn) с помощью структур данных: Построим sparse table на максимуме на массиве h; Для каждого i двоичным поиском найдем max{j | j < i и max(hj , . . . , hi−1) < hi}; Gi = j − 1.
Научимся считать G за O(n) с помощью стека: while(st.top() < h[i]) st.pop(); G[i] = st.top();
Введем понятие GR: GR[i] = min{j | j > i и h[j] > h[i]}; Теперь старое G будем обозначать как GL (то есть GL, GR — ближайшие максимумы слева и справа соответственно); Подсчитываем GR аналогично GL; Построим лес деревьев по массиву h, где GR[i] — предок
Утверждение: hi имеет смысл заменять только на hGR[i] + 1, hGR[GR[i]] + 1, . . . ; То есть для каждого элемента его возможные замены — его предки в дереве; После замены hi на hGRj [i] (j раз перешли к предку), у всех предков i между i и hGRj [i] GL стал равен i; Для данного i переберем количество предков, для которых мы станем GL; Тогда S(h) изменится на diff = Pj x=0 (i − GL[GRx [j]) + GLnew[i] − i;
Чему равно GLnew[i]?; hi мы заменили на hGRj [i] + 1; Но так как все числа четные, получаем: hGRj+1[i] >= hGRj [i] + 2 > hGRj [i] + 1 = hnew[i]; Значит GLnew[i] = GRj+1 [i]; Подставим в формулу изменения S(h): diff = Pj x=0 (i − GL[GRx [j]]); Получили, что diff равен сумме по всем предкам i, включая i; Вывод — чем больше j, тем больше diff .
Получаем сразу решение первых 4 подгрупп: Перебираем i; Хотим diff как можно больше, поэтому заменяем hi на hroot[i] , где root[i] — корень дерева с вершиной i; То есть оптимальная замена hi — на maxj>i h[j] + 1 (если этот максимум больше hi);
Чтобы решить задачу на 100 баллов, осталось сделать немного; Единственное отличие от 81 балла — не всегда можно заменять hi на hroot[i] + 1; Чтобы найти max{j | можно заменить hi на hGRj [i] + 1}, используем двоичные подъемы по дереву; Дополнительно обойдем dfs-ами все деревья и посчитаем суммы GL на префиксах путей из корня; Все остальные подсчеты остаются прежними.
- Assistant
Для решения задачи нам необходимо реализовать алгоритм, который вычисляет минимальную возможную сумму S(h) после увеличения высоты одного из воздушных потоков не более чем на m.
Вот пошаговый план решения:
-
Вычисление GL и GR:
GL[i]— индекс ближайшего элемента слева, большего, чемh[i].GR[i]— индекс ближайшего элемента справа, большего, чемh[i].- Оба массива вычисляются с помощью монотонного стека.
-
Вычисление начальной суммы S(h):
- Изначально S(h) равна сумме
(i - GL[i])для каждогоi.
- Изначально S(h) равна сумме
-
Генерация возможных вариантов увеличения:
- Для каждого элемента
iмы можем увеличитьh[i]доh[GR^j[i]] + 1(гдеGR^j[i]—j-й предок по деревуGR), при условии, что требуемое увеличение не превышаетm. - При каждом таком увеличении мы вычисляем возможное уменьшение суммы S(h), накапливая
delta_S.
- Для каждого элемента
-
Агрегация и выбор оптимального варианта:
- Собираем все возможные увеличения в список записей
(increase_needed, delta_S, i). - Сортируем этот список по возрастанию
increase_needed. - Итерируемся по списку и для каждого значения
increase_needed ≤ mобновляем максимальноеdelta_S. - Выбираем вариант с максимальным
delta_Sи соответствующимincrease_needed.
- Собираем все возможные увеличения в список записей
-
Вычисление минимальной суммы S(h):
- Если найденное максимальное
delta_Sбольше нуля, минимальная сумма S(h) равнаinitial_S - max_delta_S. - Иначе, минимальная сумма остается равной
initial_S.
- Если найденное максимальное
Ниже представлен код на C++, реализующий описанный алгоритм:
#include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; typedef long long ll; struct Record { ll increase_needed; ll delta_S; int index; Record(ll inc, ll delta, int idx) : increase_needed(inc), delta_S(delta), index(idx) {} bool operator<(const Record& other) const { return increase_needed < other.increase_needed; } }; int main() { int n; ll m; cin >> n >> m; vector<ll> h(n + 2); for (int i = 1; i <= n; ++i) { cin >> h[i]; } h[0] = 1e18; // Sentinel value for stack operations h[n + 1] = 1e18; // For GR vector<int> GL(n + 1, 0); vector<int> GR(n + 1, n + 1); vector<ll> s0(n + 1, 0); // Compute GL[i] stack<int> stk; stk.push(0); // Sentinel index for (int i = 1; i <= n; ++i) { while (!stk.empty() && h[stk.top()] <= h[i]) { stk.pop(); } if (!stk.empty()) { GL[i] = stk.top(); } else { GL[i] = 0; } stk.push(i); } // Compute initial S(h) ll initial_S = 0; for (int i = 1; i <= n; ++i) { initial_S += (i - GL[i]); } // Compute GR[i] while (!stk.empty()) stk.pop(); stk.push(n + 1); // Sentinel index for (int i = n; i >= 1; --i) { while (!stk.empty() && h[stk.top()] <= h[i]) { stk.pop(); } if (!stk.empty()) { GR[i] = stk.top(); } else { GR[i] = n + 1; } stk.push(i); } vector<Record> records; // Generate possible actions for (int i = 1; i <= n; ++i) { int node = i; ll delta_S = 0; while (true) { int parent = GR[node]; if (parent == n + 1) break; ll increase_needed = h[parent] + 1 - h[i]; if (increase_needed > m) break; delta_S += (i - GL[parent]); records.emplace_back(increase_needed, delta_S, i); node = parent; } } // Sort records by increase_needed sort(records.begin(), records.end()); ll max_delta_S = 0; for (auto& rec : records) { if (rec.increase_needed > m) break; if (rec.delta_S > max_delta_S) { max_delta_S = rec.delta_S; } } ll final_S = initial_S - max_delta_S; cout << final_S << endl; return 0; }Пояснения:
- Мы используем
long longдля хранения больших чисел, так как суммы могут превышать пределыint. - Sentinel значения (очень большие числа) используются для упрощения работы со стеком и избежания проверок на пустоту стека.
- Структура
Recordхранит информацию об одном возможном увеличении: необходимое увеличениеincrease_needed, изменение суммыdelta_Sи индекс элементаi. - Сортировка записей по
increase_neededпозволяет эффективно найти оптимальное увеличение, не превышающееm. - В конце мы выводим минимальную возможную сумму S(h) после оптимального увеличения одного из элементов массива.
Замечания:
- В данной реализации мы не используем сложные структуры данных, что позволяет сохранить код простым и понятным.
- Алгоритм работает за O(n log n), что укладывается в ограничения по времени для заданных значений n.
-