| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Задача Джонсона |
| Автор: Saratov 3.12.2005, 20:38 |
| Знакомый парень, сказал что я не смогу решить эту задачу. правда как то не получается. помогите пожалуйста. желателен код. На завод, куда поступила партия из N запчастей, используется два станка. Каждая запчасть должна сначала пройти обработку на станке I, а затем на станке II. Каждый станок обрабатывает не более 1 бутылки одновременно. Ваша задача составить такой порядок подачи бутылок на станки, чтобы время окончания работы завода было минимально. Входные данные Входной файл состоит из последовательности тестов. В первой строке теста записано натуральное N (1 <= N <= 100000). Далее в N строках записаны описания каждой детали двумя вещественными числами Ai, Bi (1 <= Ai,Bi <= 10000) -- времена обработки i-ой запчасти на первом и втором станках соответственно. Гарантируется, что сумма значений N по всем тестам не превосходит 100000. Вещественные числа задаются не более чем с 4 знаками после запятой. Выходные данные Для каждого теста выведите искомое время в отдельной строке. Во вторую строку выведите порядок подачи запчастей. Если искомых порядков несколько, выведите любой. Пример Ввод 2 3 4 10 2 6 7 10 9 8 3 1 2 4 11 6 5 12 Вывод 15.00000 1 2 44.00000 4 6 1 2 5 3 |
| Автор: amium 4.12.2005, 18:52 |
| Простейший способ это перебрать все комбинации и для каждой комбинации измерять время. И найти минимальное время с соответствующей комбиацией. |
| Автор: Гость_Saratov 5.12.2005, 13:39 |
| а ты попробуй. |
| Автор: SDenis 5.12.2005, 14:57 |
Бутылка стала запчастью ) Здорово) Все перебрать конечно не получиться, но если ввести "глубину"(т.е. количество пар которое мы перебираем начиная с текущей, то задача упроститься, а время получаемое в ответе не сильно возрастет). Есть ощущение(возможно неправильное), что начиная c "глубины" == logN ответы для полного перебора и пребора частичного будут совпадать) |
| Автор: Akina 5.12.2005, 23:24 |
| 1) преобразовать список затрат времени на 1 и 2 станке на одну деталь в список на все затребованные детали (тупое умножение) 2) Отсортировать список по убыванию разности времен пребывания на 1 и 2 станках. Задача решена. |
| Автор: Graf Zeppelin 7.1.2006, 17:20 |
| Akina А примерчик можно? |
| Автор: Fedor 7.1.2006, 18:37 |
| Вообще, это стандартная задача, часто дающаяся на олимпиадах. Saratov, ты уверен, что это не задание тебе на программирование? ;) Уже не помню, но это то ли на потоки в графах, то ли что-то подобное. Добавлено @ 18:36 Хотя при двух станках может решаться обчкновенной сортировкой. Добавлено @ 18:37 Ой, не увидел. Сорри. Имхо, Akina действительно прав. |
| Автор: maxdiver 29.1.2008, 23:23 |
| Хех, да это зодачка с саратовского сайта по олимпиадному программированию ))) Akina А зачем тут умножение? Одной сортировкой исходного массива всё решается. |