| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм решения задачи |
| Автор: pacan4ik 21.10.2012, 14:21 |
| Есть вот такая вот задача . На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое задается одним целым числом — расстоянием в метрах от начальной отметки. Все монеты расположены правее начальной отметки. Али-баба бегает по дороге и собирает монеты, начиная делать это в момент времени 0. За одну секунду он пробегает ровно один метр. У каждой монеты есть крайний срок, до которого (включительно) ее нужно подобрать, иначе монета исчезнет. Али-баба должен собрать все монеты и сделать это за минимально возможное время. Он может стартовать в любой точке прямой, собирать монеты в произвольном порядке, но обязательно нужно успеть собрать все монеты и при этом минимизировать затраченное время. Задается число n — количество монет , для каждой монеты задается по 2 целых числа, первое из которых задает положение монеты, а второе — крайний срок в секундах, за который нужно успеть собрать эту монету. Нужно найти минимальное время сбора всех монет или сказать , что собрать все монеты невозможно. Собственно , меня интересует только алгоритм решения (очень похоже на динамическое программирование , но как я не пробовал , не получается) и какие структуры данных лучше использовать . Буду благодарен за любую помощь . |