Станции проката
Вдоль улицы есть n перекрёстков, известно расстояние от начала улицы до каждого. На k из них нужно поставить станции проката так, чтобы две ближайшие станции оказались как можно дальше друг от друга. Каким может быть наибольшее такое расстояние? Для каждого k из списка нужен свой ответ.
Второй и третий тесты — 177 перекрёстков самого длинного кратчайшего маршрута через центр Алматы: 24,1 км по улицам из OpenStreetMap.
Вход
В первой строке n и q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10). Во второй — n различных расстояний в метрах, от 0 до 10⁹. В третьей — q чисел k (2 ≤ k ≤ n).
Выход
Для каждого k — наибольшее возможное расстояние между двумя ближайшими станциями.
Примеры
Пример 1
5 3 1 2 4 8 9 2 3 5
8 3 1
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Вопрос «можно ли расставить k станций так, чтобы между любыми двумя было не меньше d» решается проще, чем исходный. И если для d можно, то для любого меньшего d тоже можно.
2Идея
Ищем наибольшее d, для которого ответ «можно», двоичным поиском. Проверка жадная: первую станцию ставим на первый перекрёсток, каждую следующую — на первый перекрёсток, который отстоит от предыдущей станции хотя бы на d. Если так набралось k станций — можно.
3Разбор
Почему жадная проверка не ошибается: ставить станцию раньше не бывает хуже — у всех следующих станций остаётся больше места. Любую подходящую расстановку можно сдвинуть влево к жадной, не нарушив условия.
Здесь ищется не первое, а последнее «можно», поэтому середина берётся с округлением вверх: (lo + hi + 1) / 2. С округлением вниз при hi = lo + 1 поиск зацикливается.
3+Решение
4Сложность
Отрезок до 10⁹ — 30 проверок по O(n): O(n log D) на один k, плюс сортировка.
5Типичные ошибки
- Ставить станции через равное число перекрёстков. Перекрёстки стоят неравномерно: на маршруте по Алматы соседние перекрёстки бывают в двух метрах друг от друга, а бывают в трёх километрах; обычный промежуток — около 80 метров.
- Середина с округлением вниз. В поиске «последнего подходящего» это вечный цикл на двух соседних числах.
- Неотсортированный вход. Жадная проверка идёт слева направо и требует отсортированных расстояний.
Алгоритмы задачи
O(log D · стоимость проверки)
2 задачи
PAR
Приём
Жадные алгоритмы
Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать.
обычно O(n log n): сортировка или куча
2 задачи