Алгоритм решения задачи
Есть вот такая вот задача . На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое задается одним целым числом — расстоянием в метрах от начальной отметки. Все монеты расположены правее начальной отметки. Али-баба бегает по дороге и собирает монеты, начиная делать это в момент времени 0. За одну секунду он пробегает ровно один метр. У каждой монеты есть крайний срок, до которого (включительно) ее нужно подобрать, иначе монета исчезнет. Али-баба должен собрать все монеты и сделать это за минимально возможное время. Он может стартовать в любой точке прямой, собирать монеты в произвольном порядке, но обязательно нужно успеть собрать все монеты и при этом минимизировать затраченное время.
Задается число n — количество монет , для каждой монеты задается по 2 целых числа, первое из которых задает положение монеты, а второе — крайний срок в секундах, за который нужно успеть собрать эту монету. Нужно найти минимальное время сбора всех монет или сказать , что собрать все монеты невозможно.
Собственно , меня интересует только алгоритм решения (очень похоже на динамическое программирование , но как я не пробовал , не получается) и какие структуры данных лучше использовать . Буду благодарен за любую помощь .
Задается число n — количество монет , для каждой монеты задается по 2 целых числа, первое из которых задает положение монеты, а второе — крайний срок в секундах, за который нужно успеть собрать эту монету. Нужно найти минимальное время сбора всех монет или сказать , что собрать все монеты невозможно.
Собственно , меня интересует только алгоритм решения (очень похоже на динамическое программирование , но как я не пробовал , не получается) и какие структуры данных лучше использовать . Буду благодарен за любую помощь .
Поищи ответ в области линейного программирования. "Транспортная задача", "задача коммивояжёра" и все такое. Не исключено, что ты найдешь уже готовый алгоритм для своей задачи.