Задача 12.
Имеется N книг и два читателя, А и В, желающих прочитать эти книги. Заданы неотрицательные целые числа A[I] и B[I] такие, что читателю А (или В) потребуется A[I] (соответственно, B[I]) часов для прочтения книги I, 1 <=I <=N. Процесс чтения начинается в момент времени 0. В любой момент времени каждый читатель не может читать более одной книги и каждую книгу не могут читать оба читателя.
Для каждого читателя порядок чтения книг не имеет значения и может быть произвольным. В процессе чтения любой книги любым читателем допускаются прерывания. Это означает, что этот процесс может быть прерван в любой целочисленный момент времени и возобновлен позднее с прерванного места. В промежутке между прерыванием и последующим возобновлением процесса чтения книги читатель может читать любую не до конца прочитанную книгу.
Задано целое число К, 2<=K <=N, и книги пронумерованы таким образом, что ни один читатель не имеет права начать читать книгу J, 2<= J <= K, прежде чем книга J-1 не будет прочитана обоими читателями.
Требуется:
1. Вычислить наименьший момент времени Т, раньше которого все книги не могут быть прочитаны всеми читателями. Вывести вычисленное значение Т.
2. Построить расписание чтения книг каждым читателем, при котором не нарушается ни одно из перечисленных выше условий и процесс чтения всех книг завершается в момент времени Т. Расписание для каждого читателя вывести в виде
< РАСПИСАНИЕ ДЛЯ ЧИТАТЕЛЯ А (или В) >
<Номер книги>
<Начало>
<Конец>
. . . . . .
. . . . .
. . . . .
. . . . . .
. . . . .
. . . . .
В таблицах указанного вида необходимо указать все временные интервалы, в течение которых читатель А (или В) читает книгу и номер этой книги.
3. Постарайтесь сократить число прерываний для каждого читателя.
|
