|
0 / 0 / 0
Регистрация: 27.08.2020
Сообщений: 7
|
||||||||||
Задача на нахождение максимального кол-ва пересечений отрезков в точке (оптимизировать алгоритм)27.08.2020, 12:40. Показов 3311. Ответов 11
Метки нет (Все метки)
Добрый день!
В общем и целом есть задача и звучит она так: Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт На прямoй располагаeтся 1 ≤ N ≤ 10000 тoчек с целочислeнными кooрдинатами –10^9 ≤ Vi ≤ 10^9. Кaждой из тoчек рaзрешается сдeлать рoвно однo движениe (тaнцевальное пa) в любoм напpавлении на рaсстояние нe большe 0 ≤ L ≤ 10^8 и остановитьcя нa дрyгой пoзиции. Какоe минимaльное кoличество тoчек мoжет oстаться нa прямoй пoсле oкончания тaнца (всe точки послe танцa, oказывающиеся на oдной пoзиции, сливaются в oдну)? Формат входных данных: L N V1 V2 … VN Формат выходных данных: MinimalNumberOfPoints Примеры:
Моё видение задачи
Как я понял, задача не о точках, а об отрезках То есть точка может сдвигаться от своей позиции на длину L влево или вправо Соответственно, она образует отрезок на прямой Вся суть задачи заключается в том, чтобы найти те точки, которые вмещают максимальное кол-во отрезков, сами при этом не двигаясь Например, для тестовых входных данных это точки 3(до неё никто не дотянется) и 21(к ней дотянутся 30, 14 и 19) Соответственно, ответ 2 Я сделал, так сказать, в лоб. Вот что получилось: Мой вариант
Но он явно проигрывает по скорости исполнения, потому что при шаге в 100000 и кол-ве элементов всего лишь в 35000(от 1 до 35000) Программа на моём процессоре исполняется 4.5 секунды с оптимизациями компилятора, что явно намекает на плохой алгоритм Помогите исправить алгоритм так, чтобы он проходил тест Или подскажите, как надо такую задачу решать Хотя бы направление дайте Я понимаю, что в книге эта задача из главы "Жадные алгоритмы", но всё равно как-то для меня слишком это сложно оказалось
0
|
||||||||||
| 27.08.2020, 12:40 | |
|
Ответы с готовыми решениями:
11
Алгоритм Форда-Фалкерсона. Нахождение максимального потока сети Графы. Алгоритм DFS. Нахождение максимального количества независимых рёбер |
|
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
|
|
| 27.08.2020, 13:10 | |
|
Может я не так понял, но я бы нашел точку с минимальной(min) и максимальной(max) координатой.
Если существует отрезок [min + L, max - L](т.е. отрезки [min, min + L] и [max - L, max] не пересекаются), то если в этом отрезке существует хотя бы одна точка - ответ 3. Иначе, если длина отрезка [min, max] > L - ответ 2. Иначе ответ 1. Добавлено через 17 минут Извиняюсь, невнимательно прочитал. Не увидел что L тоже задаётся как входной параметр. Тогда предварительная сортировка массива. Дальше принцип тот же, только в первом случае прибавляем к результату 2, исключаем эти два крайних отрезка и повторяем проверки.
0
|
|
|
0 / 0 / 0
Регистрация: 27.08.2020
Сообщений: 7
|
||
| 27.08.2020, 15:34 [ТС] | ||
|
Какими тогда при этом подходе будут min и max? Первый и последний элемент сортированного массива или это должен быть какой-то локальный минимум/максимум?
0
|
||
|
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
|
|||||||
| 27.08.2020, 16:49 | |||||||
1
|
|||||||
|
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
|
|
| 27.08.2020, 17:00 | |
|
Сначала, конечно, отсортировать. Желательно ещё и одинаковые удалить (другая точка с той же координатой будет вести себя как первая).
Далее можно представить ситуацию, когда у нас есть группа точек в точке a, одна точка в точке b, и ещё группа точек в точке c. По отдельности эти 3 группы дадут к ответу +3. Если мы точку из a или из c двинем в b, то ответ тоже +3 (т.к мы одинаковые удалили, то из группы может двигаться не более одной(которая сразу стояла на этой координате)). А если мы b двинем куда-то в a или c, то ответ +2. Я этим хотел сказать, что нам все равно куда будет ходить точка - вправо/влево, главное, чтобы она попала в одну из групп точек. То есть, полагаю, алгоритм будет жадным : Первая точка сразу вправо ко второй(если не может дойти, то на L вправо). Следующие точки будут просто стремится к объединению с той, которая слева. Иначе, если не могут дойти до левой, то вправо к i+1 точке (если не может дойти, то на L вправо). Не очень уверен вообще в жадных алгоритмах, но вроде бы должно работать. Иначе, хотелось бы увидеть контрпример.
1
|
|
|
863 / 513 / 215
Регистрация: 19.01.2019
Сообщений: 1,216
|
||||||
| 27.08.2020, 17:15 | ||||||
2
|
||||||
|
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
|
||||||
| 27.08.2020, 17:37 | ||||||
|
nalbe666, то ли я не понял, то ли ваш алгоритм не так подсчитывает.
Для 0 3 0 0 0 у вас выводит 3, хотя вроде должно вывести 1. Для 1 3 1 2 3 у вас выводит 2, хотя вроде должно вывести 1. Добавлено через 10 минут Если подправить предикат сортировки так, то вроде правильно отрабатывает
1
|
||||||
|
863 / 513 / 215
Регистрация: 19.01.2019
Сообщений: 1,216
|
|
| 27.08.2020, 17:45 | |
|
zayats80888, да, спасибо, не проверил до конца.
0
|
|
|
0 / 0 / 0
Регистрация: 27.08.2020
Сообщений: 7
|
||
| 27.08.2020, 21:15 [ТС] | ||
|
Работает правильно на всех наборах, которые я пробовал А можете подсказать, что можно почитать, чтобы такие алгоритмы научиться писать? Книги какие-нибудь Может, это какой-то специфический случай более общей задачи, у которой есть какие-то алгоритмы решения?
0
|
||
|
2674 / 1336 / 480
Регистрация: 08.11.2016
Сообщений: 3,692
|
||
| 28.08.2020, 11:48 | ||
|
Роберт Седжвик - "Алгоритмы на C++". Факултативно: Герб Саттер - "Решение сложных задач на C++" и "Новые сложные задачи на C++". Перед началом занятий по этим книгам рекомендую к изучению: Эндрю Кениг, Барбара Му "Эффективное программирование на C++".
0
|
||
|
0 / 0 / 0
Регистрация: 27.08.2020
Сообщений: 7
|
|||||||||||||||||
| 09.09.2020, 20:39 [ТС] | |||||||||||||||||
|
zayats80888, всё же ваш алгоритм работает неправильно
Потому что он предполагает, что точка, к которой происходит движение, не двигается Это была ошибка в моём алгоритме и вы её унаследовали почему-то ![]() В задаче не говорится об этом В итоге я разобрался сам и вот верный итоговый вариант:
Добавлено через 7 минут
0
|
|||||||||||||||||
|
6352 / 3523 / 1428
Регистрация: 07.02.2019
Сообщений: 8,995
|
|||
| 09.09.2020, 20:57 | |||
.
0
|
|||
| 09.09.2020, 20:57 | |
|
Помогаю со студенческими работами здесь
12
Нахождение пересечений объектов типа geometry Алгоритм нахождения пересечений треков Есть ли у кого похожий алгоритм: распределения отрезков разной длины внутри отрезков фиксированной длины? Алгоритм обработки матрицы: Нахождение максимального элемента матрицы и его номера.
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда
anaschu 31.03.2026
В прикрепленном документе раздумья о том, как можно поменять модель в будущем
|
10 пpимет, которые всегда сбываются
Maks 31.03.2026
1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию.
2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .
|
Перемещение выделенных строк ТЧ из одного документа в другой
Maks 31.03.2026
Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
|
Functional First Web Framework Suave
DevAlt 30.03.2026
Sauve. IO
Апнулись до NET10.
Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта
так и в интерактивном режиме. из сложностей - чисто функциональный подход.
Решил. . .
|
|
Автоматическое создание документа при проведении другого документа
Maks 29.03.2026
Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2.
Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники".
В. . .
|
Настройка движения справочника по регистру сведений
Maks 29.03.2026
Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии.
. . .
|
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2.
При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
|
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут.
https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc
Первый документ красиво выглядит, но без схемы.
Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
|