| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [C++] Минимальное покрытие |
| Автор: Sanya 7.10.2006, 17:34 |
| Минимальное покрытие Ограничение времени: 1.0 секунды Ограничение памяти: 16 МБ Среди заданного множества отрезков прямой с целочисленными координатами концов [ Li , Ri ] необходимо выбрать подмножество наименьшей мощности, целиком покрывающее отрезок [0,M], где M – натуральное число. Исходные данные В первой строке указана константа M (1 <= M <= 5000). В последующих строках перечислены пары чисел "Li Ri" (abs(Li), abs(Ri) <= 50000), каждая пара с новой строки, числа в парах отделены друг от друга одним или несколькими пробелами. Список завершается парой чисел "0 0". i <= 100000 Результат Программа должна формировать в первой строке требуемое минимальное число отрезков из исходного множества, необходимое для покрытия отрезка [0,M]. Далее должен следовать список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe, завершающую пару [0,0] выводить не следует. Если покрытие отрезка [0,M] исходным множеством отрезков [Li,Ri] невозможно, то соледует вывести единственную фразу "No solution". Пример исходных данных Sample input #1 1 -1 0 -5 -3 2 5 0 0 Sample input #2 1 -1 0 0 1 0 0 Пример результата Sample output #1 No solution Sample output #2 1 0 1 |
| Автор: maxim1000 7.10.2006, 19:53 |
| можно попробовать вариацию на тему динамического программирования: для начала рассматриваем "полупокрытия" (термин, придуманный только что): полупокрытие - подмножество отрезков, которое полностью покрывает отрезок [0,x], x<=M цель задачи - полупокрытие для x=M далее алгоритм такой: 1. ищем полупокрытие из одного отрезка, для максимально возможного x1 2. ищем полупокрытие из двух отрезков для максимально возможного x2 и т.д., пока очередной x не будет равен M фишка в том, что для получения результатов каждого следующего шага можно использовать результаты предыдущего, из-за этого, по идее, должно шустренько работать алгоритм каждого следующего шага: 1. перебираем все неиспользованные отрезки, у которых левый конец находится левее правого конца полупокрытия с предущего шага 2. из них выбираем тот, к которого правая граница наибольшая Добавлено @ 19:54 P.S. ну если не останется неиспользованных отрезков, а правый конец полупокрытия не доберётся до M, значит, нет решений |