Доброй ночи. Я постоянно слышу о двух указателях, но толком разобраться в этом самостоятельно не смогла. Кто-нибудь может мне подробнее о них рассказать? В каких задачах они используются? Буду благодарна, если кинете ссылки на теоретические материалы :)
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 17:31:04 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Примеров задач на 2 указателя очень много. Но в голову так сразу ничего не приходить. Поэтому такой искусственный, но простой пример: есть массив из 105 положительных чисел нужно найти количество подмассивов c суммой больше либо равной k. Понятно можно перебрать левую границу и подбирать правую бинпоиском. Это решение будет за O(n * logn). Можно по другому заведем два числа lf = 0 и rg = 0 (как раз два указателя) теперь будем увеличивать lf. После каждого увеличения lf будем двигать (увеличивать) rg пока сумма на подотрезке не станет больше либо равна k. Это будет работать за O(n). В качестве более сложного примера задача о нахождении треугольника наибольшей площади среди заданных n точек.
то есть суть в том, чтобы хранить одновременно левую и правую границу? я кажется не допоняла ваш пример, разве он не за О(n^2) работает? (для каждой левой увеличивать правую?)
В том и суть, что асимптотика линейная. Левая и правая границы двигаются только вправо, а значит, что каждая сделает только O(N) операций.
spasibo) teper' ponyala)
Вся фишка в том что rg не надо сбрасывать при каждом увеличении lf. Поэтому решении будет работать ровно за 2 * n действий
спасибо) а в задаче про треугольники в качестве rg используется 3-я точка?
а как в более сложных задачах понять, что этот метод сработает? то есть как понять, что rg не надо сбрасывать? мне почему-то это не слишком очевидно)
Это приходит с опытом) Обычно срабатывает что-то вроде "если какое-то условие неверно для интервала [l;r], то для всех меньших оно тоже неверно". Тогда можно двигать вправо l и бессмысленно двигать когда-либо r обратно.
понятненько) спасибо большое)
Ну это уже от задачи зависит. Очень часто на монотонных фукнциях где можно решать бинпоиском можно и указателями, таким образом пропадает логарифм из асимптотики.
Про точки нужно решать так: построим выпуклую оболочку всех точек. Утверждение что искомый треугольник имеет вершины в выпуклой оболочке. Теперь перебираем первую точку по выпуклой оболочке произвольным образом. Перебираем вторую точку в порядке по или против часовой стрелки. А третью двигаем указателем в том же порядке что и вторую, пока ответ улучшается. Таким образом решение за O(n2). Ну правильность этого еще нужно доказать. Вроде про это рассказывалось на лекциях в Харькове (кажется лекция Левина).
спасибо) очень четкое объяснение)
Вот тут пишут, что после построения выпуклой оболочки, треугольник наибольшей площади ищется за O(n). Решение тоже через 3 указателя, но перебирается только первый, а два остальных увеличиваются пока улучшается ответ.
Проверил на задаче http://codeforces.me/contest/682/problem/E алгоритм Добкина-Снайдера действительно работает причем за О(n)! Спасибо за линк!
У нас на обласной олимпиаде была эта задача, только уже была построена выпуклая оболочка (был дан выпуклый многоугольник, нужно найти треугольник...)
Отличный пример, реально помог. Спасибо!
Ещё пример. На окружности отмечено N точек, они даны в порядке обхода по часовой стрелке. Нужно за линейное время (O (N)) найти пару наиболее удалённых точек.
How can we solve this ..??
Самый простой пример. Дан отсортированный массив, нужно найти в нем 2 числа, сумма которых равна нулю например. Решать можно за O (N) как раз двумя указателями.
спасибо за пример
Из классики в MergeSort, например.
спасибо) не знала, что это и есть 2 указ)
Вот еще задача на три указателя, достаточно известная если не ошибаюсь была на каком-то финале.
Есть k эльфов и n оленей. У каждого эльфа и у каждого оленя есть свои характеристики: ai — у эльфов, bj — у оленей. Для того чтобы составить рождественскую повозку, нужно взять два оленя и одного эльфа, при том так чтобы bj1 < ai < bj2, где j1, j2, i — номера оленей и эльфов. Сколько пар повозок мы сумеем составить?
Авторское решение — O(nlogn)
P.S. если у кого есть точное условие — напишите
Не знаю откуда ты знаешь задачи с финала но лучше спрячь коммент под спойлер.
Думаешь, с будущего финала задача?))
)) Думаю с прошедшего, поэтому не стоит палить задачу.
ВКОШП 2005, расходимся :)
Это?
Именно она.
Ещё пример. CR #112: C. Еще одна строковая задача можно решать так.
Обобщается ли утверждение про то, что треугольник максимальной площади можно искать тремя указателями на произвольный m-угольник?