Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Задача Джонсона 
:(
    Опции темы
Saratov
Дата 3.12.2005, 20:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 1.12.2005

Репутация: нет
Всего: нет



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


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


PM MAIL   Вверх
amium
Дата 4.12.2005, 18:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 19
Регистрация: 2.12.2005

Репутация: нет
Всего: нет



Простейший способ это перебрать все комбинации и для каждой комбинации измерять время. И найти минимальное время с соответствующей комбиацией.
PM MAIL   Вверх
Гость_Saratov
Дата 5.12.2005, 13:39 (ссылка)    |    (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered











а ты попробуй.
  Вверх
SDenis
Дата 5.12.2005, 14:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 3.12.2005

Репутация: нет
Всего: нет



Бутылка стала запчастьюsmile) Здоровоsmile) Все перебрать конечно не получиться, но если ввести "глубину"(т.е. количество пар которое мы перебираем начиная с текущей, то задача упроститься, а время получаемое в ответе не сильно возрастет). Есть ощущение(возможно неправильное), что начиная c "глубины" == logN ответы для полного перебора и пребора частичного будут совпадатьsmile)
PM MAIL   Вверх
Akina
Дата 5.12.2005, 23:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454



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

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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
Graf Zeppelin
Дата 7.1.2006, 17:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 130
Регистрация: 28.3.2004

Репутация: нет
Всего: 1



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

--------------------
Jah, help me!
PM MAIL   Вверх
Fedor
Дата 7.1.2006, 18:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Днепрянин
****


Профиль
Группа: Участник
Сообщений: 2090
Регистрация: 8.2.2003
Где: Великий

Репутация: 2
Всего: 32



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


--------------------
Мы - Днепряне. Мы всех сильней.
PM ICQ   Вверх
maxdiver
Дата 29.1.2008, 23:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18



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

Akina
А зачем тут умножение? Одной сортировкой исходного массива всё решается.
PM MAIL WWW ICQ   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0853 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.