Тренировочная сессия 12: скользящее окно по отсортированному массиву СЕССИЯ

Что тренируем сегодня

На сессии 10 два указателя шли навстречу друг другу и считали пары. Сегодня оба указателя едут в одну сторону — это уже не подсчёт пар, а скользящее окно: подотрезок отсортированного массива, который расширяется справа, пока условие выполняется, и подтягивается слева, когда нарушается. Приём выглядит почти тем же самым, но опирается на другое свойство и решает другой класс задач — «выбрать лучший набор, укладывающийся в ограничение».

Обе задачи на окно, но ограничения в них разной природы. В первой это разброс: элементы окна не должны отличаться больше чем на заданную величину, и проверка сводится к сравнению двух краёв. Во второй — стоимость: окно допустимо, пока хватает бюджета подтянуть все его элементы к правому краю, и цена окна пересчитывается на лету. Второй вид тоньше: одна и та же формула стоимости меняется при каждом сдвиге любой из границ.

Коридор сегодня ~CF 1500–1600. Обе задачи входят в набор, который стоит уметь писать «на автомате» — они встречаются в бесчисленных вариациях.

---

Теория

Скользящее окно по отсортированному массиву. Оба указателя едут в одну сторону: правый впускает элементы, пока условие держится, левый выталкивает их, когда условие ломается.

Когда применять:

• надо выбрать подмножество элементов, у которого разброс значений ограничен («разница между максимумом и минимумом меньше d»), и максимизировать какую-то сумму по выбранным;
• порядок исходных элементов не важен — важны только значения (иначе сортировать нельзя, и приём отпадает);
• элементов до $10^5$–$10^6$, перебор пар границ ($O(n^2)$) не проходит.

Ключевое наблюдение: после сортировки по значению оптимальный набор — это непрерывный отрезок. Если мы взяли два элемента, то любой элемент между ними по значению можно взять бесплатно: разброс от этого не увеличится, а сумма не уменьшится (когда веса неотрицательны). Значит перебирать нужно не подмножества, а отрезки.

Как решать:

1. Отсортировать по значению, по которому задано ограничение.
2. Вести два указателя: левый — начало окна, правый — первый элемент за окном.
3. Двигать правый вперёд, пока условие «разброс укладывается в ограничение» выполняется, добавляя элементы в текущую сумму.
4. Когда двигать правый дальше нельзя — обновить ответ, затем сдвинуть левый на один и вычесть его вклад из суммы.

Почему это линейно: правый указатель никогда не откатывается назад. Если при левой границе l окно доехало до r, то при l + 1 условие только ослабевает (минимум окна вырос), значит правый снова стартует не раньше r. Каждый указатель проходит массив ровно один раз — итого $O(n)$ после сортировки.

Сумму окна можно держать двумя способами: накапливать на лету (прибавлять при входе элемента, вычитать при выходе) или заранее посчитать префиксные суммы и брать разность. Оба варианта равноценны; первый короче, второй нагляднее при отладке.

Каркас приёма — максимальная сумма по окну с разбросом меньше d:

Где ошибаются в узнавании: путают «разброс внутри набора» с «разницей соседних элементов». Условие вида «в наборе нет двух значений с разницей больше d» — это ограничение на максимум минус минимум, то есть на края окна, а не на соседние пары.

Второй вид ограничения — стоимость окна. Разброс проверяется по двум краям и потому почти бесплатен. Гораздо чаще встречается ограничение вида «окно допустимо, пока хватает бюджета сделать все его элементы одинаковыми» — и здесь проверка зависит от всех элементов сразу.

Считать её на каждом шаге заново нельзя: это вернёт квадрат. Спасает то, что стоимость выражается через сумму окна. Чтобы подтянуть все элементы окна [l, r] к значению правого края, нужно

стоимость = a[r] * (длина окна) − (сумма элементов окна)

Сумма окна поддерживается на лету: прибавили при входе элемента, вычли при выходе. Значит вся проверка — две арифметические операции, и весь проход по-прежнему линеен.

Почему подтягивать надо именно к правому краю: элементы отсортированы, увеличивать разрешено, а уменьшать нет. Значит общее значение обязано быть не меньше максимума окна, а брать его больше максимума бессмысленно — это только увеличит стоимость. Кстати, отсюда же следует, что для равных ответов минимальное значение достигается на самом левом подходящем окне — полезно, когда в условии просят «при равенстве выбрать наименьшее».

Почему правая граница никогда не откатывается. Свойство, на котором держится линейность, стоит уметь формулировать точно: если окно [l, r] допустимо, то допустимо и любое его подокно. Для разброса это очевидно, для стоимости — чуть менее: выкидывая левый элемент, мы уменьшаем и длину, и сумму, но стоимость при этом не растёт, потому что выкинутый элемент был самым маленьким и требовал самой большой доплаты. Как только это свойство есть, левому указателю никогда не нужно возвращаться назад, а правому — тем более.

Где приём перестаёт работать. Ровно там, где ломается свойство выше. Если условие может восстановиться при расширении окна — например, ограничение на чётность суммы или «в окне должно быть ровно k различных значений», — то сдвиг границы вперёд перестаёт быть безвозвратным, и одного прохода не хватит. Второй частый случай — когда сортировать нельзя, потому что условие привязано к исходным позициям; тогда окно всё ещё возможно, но уже по исходному массиву, и «разброс = края окна» перестаёт работать.

С чем путают. На сессии 10 указатели шли навстречу друг другу и поддерживали пару границ; сегодня они идут в одну сторону и поддерживают отрезок. Признак различения — в вопросе: «сколько пар / выбрать два конца» — встречные; «самый длинный или самый выгодный непрерывный кусок» — окно. Второй сосед — бинарный поиск по ответу: он тоже отвечает на «какой максимум достижим», но перебирает сам ответ, а не набор. Если проверку «достижимо ли значение $x$» естественно написать за линию, а перебирать надо именно ответ, а не окно — берут бинпоиск; мы его разбирали на сессии 5 и вернёмся к нему на «Пике».

Сложность приёма: $O(n \log n)$ на сортировку плюс $O(n)$ на проход — сортировка и доминирует.

---

Задача 1 — CF ~1500 — «Kefa and Company»

Что дано

У каждого из n друзей известны две величины: количество денег m[i] и «фактор дружбы» s[i]. Нужно позвать в компанию некоторое подмножество друзей так, чтобы никто не чувствовал себя бедным: друг чувствует себя бедным, если в компании есть кто-то, у кого денег на d или больше больше, чем у него.

Требуется максимизировать суммарный фактор дружбы приглашённых.

Формат ввода:

• Строка 1: два целых числа n и d ($1 \le n \le 10^5$, $1 \le d \le 10^9$).
• Каждая из следующих n строк: два числа m[i] и s[i] ($0 \le m_i, s_i \le 10^9$).

Формат вывода: одно число — максимальный суммарный фактор дружбы.

Пример 1:

Ввод:
4 5
75 5
0 100
150 20
75 1

Вывод:
100

Пример 2:

Ввод:
5 100
0 7
11 32
99 10
46 8
87 54

Вывод:
111

Разберём на примере

Возьмём пример 1: d = 5, друзья (75, 5), (0, 100), (150, 20), (75, 1).

Условие «никто не чувствует себя бедным» удобнее переписать через края: в компании не должно быть двух друзей, у которых разница денег не меньше d. А поскольку максимальная разница в наборе — это максимум минус минимум, всё условие сводится к одному неравенству:

максимум денег в компании − минимум денег в компании < d

Отсортируем друзей по деньгам: (0, 100), (75, 5), (75, 1), (150, 20). Теперь любой допустимый набор — непрерывный отрезок этого списка: если в компанию взяты друзья с деньгами 0 и 75, то друга с 75 можно взять бесплатно — на разброс он не влияет, а сумму только увеличивает.

Переберём отрезки, укладывающиеся в d = 5:

Отрезок [0, 75] уже недопустим: разброс 75 не меньше 5. Максимум — 100, что и есть ответ.

В примере 2 d = 100, а разброс всего массива равен 99 — влезают все пятеро сразу, ответ равен сумме всех факторов: 7 + 32 + 10 + 8 + 54 = 111.

Идея решения

Алгоритм в одну фразу: отсортировать друзей по деньгам и провести по массиву скользящее окно, в котором разница между крайними значениями меньше d, поддерживая сумму факторов на лету и запоминая максимум.

Почему это работает. Первое — сведение условия к краям: «никто не чувствует себя бедным» равносильно max − min < d, потому что худшая пара в наборе — это как раз самый богатый и самый бедный. Второе — непрерывность: после сортировки оптимальный набор всегда можно расширить до отрезка. Действительно, если в наборе есть элементы со значениями x и y (x ≤ y), то любой элемент со значением между ними не меняет ни минимума, ни максимума, а фактор дружбы неотрицателен, значит добавлять его выгодно (или, по крайней мере, не вредно). Отсюда достаточно перебирать отрезки.

Третье — линейность прохода: при сдвиге левой границы вправо минимум окна не уменьшается, поэтому граница допустимости правого края не может уехать влево. Значит правый указатель монотонен, и оба указателя вместе делают не больше 2n шагов.

Про типы. Факторов до $10^5$ штук, каждый до $10^9$ — сумма доходит до $10^{14}$, 32-битный тип переполняется.

Псевдокод

прочитать n, d и пары (m[i], s[i])
отсортировать пары по m

ответ = 0
сумма = 0
l = 0

для r от 0 до n-1:
    сумма = сумма + s[r]

    // подтягиваем левую границу, пока разброс не укладывается
    пока m[r] - m[l] >= d:
        сумма = сумма - s[l]
        l = l + 1

    ответ = max(ответ, сумма)

вывести ответ

Код решения

Комментарии по реализации. Сортировка пары «деньги, фактор» по умолчанию идёт по первому элементу — это ровно то, что нужно; порядок друзей с одинаковыми деньгами не важен. Сумма окна поддерживается на лету, поэтому префиксные суммы не нужны. Ответ инициализируется нулём, а не «минус бесконечностью»: пустая компания допустима, и её суммарный фактор равен нулю (при неотрицательных факторах это ничего не портит).

Проверка на примерах

Пример 1: после сортировки [(0,100), (75,5), (75,1), (150,20)], d = 5.

Наш вывод: 100 — совпадает с ожидаемым.

Пример 2: после сортировки [(0,7), (11,32), (46,8), (87,54), (99,10)], d = 100. Разброс всего массива 99 − 0 = 99 < 100, поэтому левая граница ни разу не сдвигается, и сумма растёт до 7 + 32 + 8 + 54 + 10 = 111.

Наш вывод: 111 — совпадает с ожидаемым.

Крайние случаи

• n = 1. Единственный друг всегда допустим, ответ равен его фактору.
• Все деньги одинаковые. Разброс нулевой, берём всех — ответ равен сумме всех факторов.
• d = 1. Допустимы только группы с одинаковым количеством денег: разброс обязан быть строго меньше единицы, то есть нулевым.
• Нулевые факторы. Ответ может быть нулевым; инициализация ответа нулём это учитывает.
• Огромный разброс денег. Левая граница догоняет правую — окно из одного элемента; цикл while обязан корректно останавливаться при l == r.
• Максимальные значения. $n = 10^5$, все факторы по $10^9$ — сумма $10^{14}$, тест на 64-битную арифметику.

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

1. Считать в 32-битном типе. Сумма до $10^{14}$ — переполнение на большом тесте.
2. Понимать условие как ограничение на соседние элементы. Требование именно на края набора: максимум минус минимум.
3. Использовать нестрогое сравнение. «Бедный, если разница не меньше d» — значит допустимо строгое max − min < d; в коде это while (m[r] − m[l] >= d).
4. Перебирать пары границ окна. Логика верна, но $O(n^2)$ на $10^5$ элементов не проходит.
5. Откатывать правый указатель назад. Признак того, что скользящее окно написано как двойной цикл: время сразу становится квадратичным.
6. Сортировать по фактору дружбы. Ограничение задано на деньги; сортировка по другому полю ломает и непрерывность оптимального набора, и монотонность окна.

Сложность

Время: $O(n \log n)$ — сортировка; проход окном $O(n)$. Память: $O(n)$ — массив пар.

---

Задача 2 — CF ~1600 — «To Add or Not to Add»

Что дано

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

Формат ввода:

• Строка 1: два целых числа n и k ($1 \le n \le 10^5$, $0 \le k \le 10^9$).
• Строка 2: n целых чисел a[1] … a[n] ($|a_i| \le 10^9$).

Формат вывода: два числа через пробел — максимальное количество одинаковых элементов и минимальное значение, на котором этот максимум достигается.

Пример 1:

Ввод:
5 3
6 3 4 0 2

Вывод:
3 4

Пример 2:

Ввод:
3 4
5 5 5

Вывод:
3 5

Пример 3:

Ввод:
5 3
3 1 2 2 1

Вывод:
4 2

Разберём на примере

Возьмём первый пример: массив 6 3 4 0 2, бюджет k = 3. Отсортируем: 0 2 3 4 6.

Первое наблюдение — прибавлять можно только вверх. Значит если мы решили сделать несколько элементов равными значению x, то годятся лишь те, что не превосходят x, и каждый обойдётся в x − a[i] операций.

Второе наблюдение — какие именно элементы выгодно собирать в группу. Пусть мы целимся в значение x. Чем ближе элемент к x снизу, тем он дешевле. Значит выгодные кандидаты — это подряд идущие элементы отсортированного массива, заканчивающиеся на последнем, который не больше x. Никакого смысла «перепрыгивать» через элемент нет: пропущенный элемент дешевле любого из тех, что лежат левее него.

Третье наблюдение — какое x вообще имеет смысл проверять. Пусть группа выбрана. Поднимать её до значения выше её максимума бессмысленно: это просто дороже, а количество одинаковых элементов не меняется. Значит целевое значение всегда можно взять равным максимуму группы, то есть одному из чисел массива. Проверять миллиард произвольных x не нужно — достаточно n кандидатов.

Из трёх наблюдений и получается окно. Правая граница — тот самый элемент, до которого подтягиваем; левая граница ползёт вправо, пока стоимость не влезает в бюджет. Пройдём пример:

• Окно [0]. Подтягивать некого, стоимость 0. Одинаковых — 1, значение 0.
• Окно [0, 2]. Надо поднять 0 до 2 — это 2 операции, влезает. Одинаковых 2, значение 2.
• Окно [0, 2, 3]. Стоимость: 3·3 − (0 + 2 + 3) = 9 − 5 = 4, а бюджет 3 — не влезает. Двигаем левую границу: окно [2, 3], стоимость 3·2 − 5 = 1. Влезает, одинаковых 2 — не лучше рекорда.
• Окно [2, 3, 4]. Стоимость 4·3 − (2 + 3 + 4) = 12 − 9 = 3, ровно бюджет. Одинаковых 3, значение 4 — новый рекорд.
• Окно [2, 3, 4, 6]. Стоимость 6·4 − 15 = 9 — много. Сдвигаем левую: [3, 4, 6] → 6·3 − 13 = 5, много; [4, 6] → 6·2 − 10 = 2, влезает. Одинаковых 2 — не рекорд.

Ответ: 3 4 — совпадает с эталоном. Обратите внимание, что три четвёрки получились из элементов 2, 3 и 4, а вовсе не из тех, что были ближе всего к рекорду по частоте.

Идея решения

Алгоритм в одну фразу: отсортировать массив и провести по нему окно, поддерживая сумму элементов; для каждой правой границы сдвигать левую до тех пор, пока стоимость подтягивания окна к правому краю не уложится в k, и обновлять рекорд длины.

Почему целевое значение — всегда элемент массива. Пусть оптимальный ответ достигается на значении x, и группа собранных элементов имеет максимум m ≤ x. Заменим x на m: все элементы группы по-прежнему не превосходят цели, а стоимость каждого уменьшилась на x − m. Количество одинаковых элементов не изменилось, стоимость не выросла — значит m не хуже. А раз в условии при равенстве требуется наименьшее значение, замена ещё и обязательна.

Почему группа — непрерывный отрезок. Пусть в группу с целью x вошёл элемент a[i], а более близкий к x элемент a[j] (a[i] \le a[j] \le x) — нет. Поменяем их местами: стоимость подтягивания a[j] не больше, чем у a[i], размер группы тот же. Повторяя такие замены, придём к непрерывному отрезку отсортированного массива, упирающемуся в цель справа.

Почему хватает одного прохода. Стоимость окна монотонна по обеим границам: сдвиг правой границы вправо её только увеличивает (добавляется новый элемент, и заодно растёт цель), сдвиг левой вправо — только уменьшает. Поэтому, найдя для правой границы r минимальное допустимое l, для r + 1 можно продолжать с того же l — возвращаться назад никогда не понадобится.

Почему при равенстве длины рекорд не обновляется. Мы идём слева направо, и правая граница — это и есть кандидат-значение. Первое окно данной длины встречается на наименьшем возможном значении, поэтому обновлять рекорд надо строгим неравенством cnt > best. Замена на >= тихо ломает вторую половину ответа, оставляя первую верной, — противная ошибка, потому что на первом примере она незаметна.

Псевдокод

прочитать n, k и массив a
отсортировать a по возрастанию

best_cnt = 1, best_val = a[0]
left = 0, sum = 0

для right от 0 до n-1:
    sum += a[right]
    пока a[right] * (right - left + 1) - sum > k:    // окно слишком дорогое
        sum -= a[left]
        left += 1
    если (right - left + 1) > best_cnt:              // строго больше: при равенстве
        best_cnt = right - left + 1                  // оставляем меньшее значение
        best_val = a[right]

вывести best_cnt, best_val

Код решения

Комментарии по реализации. Всё, что участвует в формуле стоимости, — 64-битное. Произведение a[right] * длина доходит до $10^9 \cdot 10^5 = 10^{14}$, и в 32-битном типе оно переполняется задолго до того, как это станет заметно на маленьких тестах. Элементы могут быть отрицательными, но на алгоритм это не влияет: формула со суммой одинаково работает и для отрицательных значений, а сортировка ставит их в начало. Начальные значения рекорда — единица и наименьший элемент: один элемент можно оставить в покое всегда, а меньшего значения, чем a[0], в ответе быть не может.

Проверка на примерах

Пример 1: a = 0 2 3 4 6 после сортировки, k = 3.

Наш вывод: 3 4 — совпадает с ожидаемым.

Пример 2: a = 5 5 5, k = 4. Окно растёт до всех трёх элементов, стоимость 5·3 − 15 = 0 — влезает всегда. Рекорд обновляется на длине 3 при значении 5. Прибавлять всем по единице и получить три шестёрки тоже можно, но это дороже и, главное, значение больше — а при равенстве количества нужно наименьшее.

Наш вывод: 3 5 — совпадает с ожидаемым.

Пример 3: a = 1 1 2 2 3 после сортировки, k = 3.

Наш вывод: 4 2 — совпадает с ожидаемым. Здесь хорошо видно, зачем нужно строгое сравнение: окно длины 3 встретилось дважды, и рекорд остался за первым, с меньшим значением.

Крайние случаи

• k = 0. Операции запрещены; ответ — самая частая величина в массиве и её значение. Окно при этом схлопывается до групп одинаковых элементов.
• n = 1. Ответ 1 и само значение. Стартовая инициализация рекорда обязана это покрывать: цикл сравнивает строго, поэтому без корректного старта вывод окажется пустым.
• Все элементы равны. Стоимость окна всегда ноль, ответ — n и само значение.
• Отрицательные элементы. Формула не меняется. Единственное место, где легко ошибиться, — инициализация best_val нулём вместо a[0].
• Максимальный разброс ($-10^9$ и $10^9$ рядом). Проверка на переполнение: произведение доходит до $10^{14}$.
• k огромно, а элементов мало. Окно охватывает весь массив, ответ — n и максимальный элемент.

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

1. 32-битная арифметика в формуле стоимости. Произведение до $10^{14}$; ошибка тихая и на примерах из условия не видна.
2. Нестрогое сравнение при обновлении рекорда. Количество получится верным, а значение — завышенным; ровно тот случай, когда «почти правильно» означает неверный ответ.
3. Пересчитывать стоимость окна суммированием заново. Логика верна, но это возвращает $O(n^2)$ и превышение лимита времени на $10^5$ элементах.
4. Подтягивать окно к левому краю. Уменьшать элементы нельзя, поэтому цель обязана быть не меньше максимума окна, то есть равна правому краю.
5. Перебирать целевое значение среди всех чисел от минимума до максимума. Диапазон до $2 \cdot 10^9$ — решение не уложится; кандидатов ровно n.
6. Забыть отсортировать. Без сортировки «непрерывный отрезок» перестаёт быть оптимальным набором, и весь приём разваливается.

Сложность

Время: $O(n \log n)$ — сортировка, плюс линейный проход окна. Память: $O(n)$ — сам массив; дополнительной памяти проход не требует.

---

Самостоятельная тренировка

Все четыре — на сегодняшний приём: в каждой после сортировки нужно вести окно, у которого одна граница впускает элементы, а другая выталкивает.

• Codeforces 253B «Physics Practical» (~CF 1400) — дан набор измерений; итог считается корректным, если наибольшее значение не превышает наименьшее более чем вдвое; нужно выбросить как можно меньше измерений, чтобы условие выполнилось. Подсказка: после сортировки остающийся набор — непрерывный отрезок, и его правая граница монотонна по левой.
• Codeforces 1462E1 «Close Tuples (easy version)» (~CF 1500) — нужно посчитать количество троек элементов, у которых максимум отличается от минимума не больше чем на два. Подсказка: окно даёт для каждого левого элемента границу допустимых правых, а дальше остаётся комбинаторика — сколько пар можно выбрать внутри найденного куска.
• Codeforces 1198A «MP3» (~CF 1600) — можно оставить только значения из выбранного диапазона, всё меньшее и большее заменяется на его границы; количество различных значений в диапазоне ограничено сверху, и нужно минимизировать число изменённых элементов. Подсказка: окно ведётся не по элементам, а по списку различных значений, а «стоимость» окна — сумма их кратностей.
• Codeforces 1833F «Ira and Flamenco» (~CF 1700) — нужно посчитать количество групп ровно из m элементов с попарно различными значениями, у которых разброс меньше m. Самая техничная в наборе: окно то же самое, но ответ собирается произведением кратностей, и при сдвиге левой границы приходится делить — то есть умножать на обратный элемент по модулю.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

Главное сегодня — не сама конструкция из двух указателей, а свойство, которое делает её законной: любое подокно допустимого окна тоже допустимо. Проверять это свойство стоит словами, до кода, — ровно как монотонность перед бинарным поиском. Если оно есть, окно решает задачу за линию; если нет, приём молча выдаёт неверный ответ.

На следующей тренировке — снова деревья, и снова жадность: выбираем вершины по «выгоде», которая считается одним обходом.