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

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

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

 
Сообщений: 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, если ей поспать не удастся.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача оптимизации производства в случае долговременного промежутка гость Математические алгоритмы (другое) 1 14.01.2010 00:19
Более оптимальный алоритм определения принадлежности точки полигону, чем трассировка wDevil Математические алгоритмы 6 10.12.2009 17:57
Поиск самого длинного пути в ориентированном графе terlan Графы 11 26.11.2009 01:27
Сравнение времени работы leahov Сортировка и поиск 3 29.05.2008 10:42
Подскажите, может существует другой алгоритм определения ширины многоугольника ViniPuh Математические алгоритмы 2 18.02.2008 19:55