Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.05.2010, 14:20
гость

 
Сообщений: n/a

Помогите придумать алгоритм
Помогите придумать алгоритм для задачи:
Няня укладывает спать детей. Но самой ей поспать никак не удается: не успевает она уложить спать одних, как просыпаются другие…

У няни N детей, и все они очень разные. Она уже запомнила, сколько минут ей нужно, чтобы уложить спать k-го ребенка (обозначим это время через ak), и сколько минут после этого он будет спать (обозначим это время через bk). Сама няня может спать, только когда спят все дети.

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

Например, пусть есть всего 2 ребенка: a1=1, b1=10, a2=10, b2=20. Если она сначала начнет укладывать первого ребенка, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго, то затем она успеет уложить первого и получит целых 10 минут отдыха.

Технические условия

Входные данные

Первая строка содержит N (1 ≤ N ≤ 100000). Вторая строка содержит натуральные числа a1 … an , третья - b1 … bn . Числа не превосходят 109 и отделяются друг от друга пробелами.

Выходные данные

Единственная строка должна содержать число T, равное максимально возможному времени сна няни, либо 0, если ей поспать не удастся.
  #2  
Старый 09.05.2010, 18:07
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Для начала стоит придумать осмысленное название темы.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите расшифровать алгоритм kuzja Сортировка и поиск 10 29.11.2009 19:14
помогите улучшить алгоритм w-x-t Реализация, исходники, языки 9 16.11.2009 01:11
Помогите найти алгоритм Бизнесмэн Математические алгоритмы 11 08.08.2009 08:58
Помогите найти алгоритм! гость Вычислительная геометрия 6 20.04.2009 17:02
Помогите найти алгоритм rom@rio Обработка изображений, звук, графика 1 16.03.2008 08:17