Знакомый парень, сказал что я не смогу решить эту задачу. правда как то не получается. помогите пожалуйста. желателен код.


На завод, куда поступила партия из 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

Простейший способ это перебрать все комбинации и для каждой комбинации измерять время. И найти минимальное время с соответствующей комбиацией.

а ты попробуй.

Бутылка стала запчастью) Здорово) Все перебрать конечно не получиться, но если ввести "глубину"(т.е. количество пар которое мы перебираем начиная с текущей, то задача упроститься, а время получаемое в ответе не сильно возрастет). Есть ощущение(возможно неправильное), что начиная c "глубины" == logN ответы для полного перебора и пребора частичного будут совпадать)

1) преобразовать список затрат времени на 1 и 2 станке на одну деталь в список на все затребованные детали (тупое умножение)
2) Отсортировать список по убыванию разности времен пребывания на 1 и 2 станках.

Задача решена.

Akina
А примерчик можно?

Вообще, это стандартная задача, часто дающаяся на олимпиадах. Saratov, ты уверен, что это не задание тебе на программирование? ;) Уже не помню, но это то ли на потоки в графах, то ли что-то подобное.
Добавлено @ 18:36
Хотя при двух станках может решаться обчкновенной сортировкой.
Добавлено @ 18:37
Ой, не увидел. Сорри. Имхо, Akina действительно прав.

Хех, да это зодачка с саратовского сайта по олимпиадному программированию )))

Akina
А зачем тут умножение? Одной сортировкой исходного массива всё решается.