Лучшие помощники
- Megamozg 2205 б
- Matalya1 1800 б
- DevAdmin 1720 б
- arkasha_bortnikov 900 б
- Dwayne_Johnson 870 б
15 марта 2023 10:13
410
/*14.1. Бонни и Клайд (6) Задача выполнена студентом ПС 21 Желаевым Денисом.Бонни и Клайд задумали ограбить в некотором городе два банка. Все N банков в этом городе находятся на его главной улице.Для каждого i-го банка известны расстояние от начала улицы Xi и имеющаяся сумма денег Wi. Чтобы было меньше шума,Бонни и Клайд собираются выбрать такую пару банков, чтобы расстояние между ними было не менее d.Вместе с тем они хотят, чтобы сумма денег в обоих банках оказалась максимальной. Как это сделать?
1
ответ
Для решения данной задачи можно использовать алгоритм двух указателей (two pointers).
Сначала необходимо отсортировать массив банков по расстоянию от начала улицы (Xi). Затем можно пройти по массиву с двух концов с помощью двух указателей (left и right), начиная с самых дальних банков.
На каждом шаге необходимо проверять, что расстояние между банками (Xi - Xj) не меньше d. Если это условие выполняется, то можно суммировать деньги в обоих банках (Wi + Wj) и сравнить с максимальной суммой, найденной до этого. Если текущая сумма больше, то обновляем максимальную сумму.
Алгоритм завершается, когда указатели встретятся. В этом случае будет найдена максимальная сумма денег в паре банков, удовлетворяющих условию на расстояние.
Временная сложность алгоритма составляет O(nlogn) за сортировку массива и O(n) за проход по массиву, то есть общая сложность O(nlogn).
Сначала необходимо отсортировать массив банков по расстоянию от начала улицы (Xi). Затем можно пройти по массиву с двух концов с помощью двух указателей (left и right), начиная с самых дальних банков.
На каждом шаге необходимо проверять, что расстояние между банками (Xi - Xj) не меньше d. Если это условие выполняется, то можно суммировать деньги в обоих банках (Wi + Wj) и сравнить с максимальной суммой, найденной до этого. Если текущая сумма больше, то обновляем максимальную сумму.
Алгоритм завершается, когда указатели встретятся. В этом случае будет найдена максимальная сумма денег в паре банков, удовлетворяющих условию на расстояние.
Временная сложность алгоритма составляет O(nlogn) за сортировку массива и O(n) за проход по массиву, то есть общая сложность O(nlogn).
0
·
Хороший ответ
15 марта 2023 10:14
Остались вопросы?
Еще вопросы по категории Информатика
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 26 -символьного н...
Составьте для исполнителя Чертёжник алгоритм рисования узора. Учитывайте смену цветов . Используйте алгоритм Квадрат из задани 19.1...
Информацию,достаточную для решения поставленной задачи,называют: а)полезной б)полной в)актуальной г)понятной...
Решите, пожалуйста 1) Информационное сообщение на русском языке, первоначально записанное в 8-битовом коде КОИ-8, было перекодировано в 16-битовую код...
Текст,содержащий 8192 знака (с пробелами),закодирован с помощью алфавита,содержащего 128 символов.Сколько килобайтов занимает в памяти этот текст? С Р...