Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Сортировка >> Номер 12

[Назад]    [Содержание ]    [Вперед]

  


Номер 12


  Условие: Номер 12


Задача 12. В музее регистрируется в течение дня время прихода и ухода каждого посетителя. Таким образом за день получены N пар значений, где первое значение в паре показывает время прихода посетителя и второе значения - время его ухода. Найти промежуток времени, в течение которого в музее одновременно находилось максимальное число посетителей.

  Решение задачи: Номер 12


Решение задачи 12. Будем представлять посещение музея посетителем в виде отрезка [время_прихода_посетителя, время_ухода_посетителя]. Надо найти множество точек, принадлежащих максимальному числу отрезков (они и будут составлять тот промежуток (промежутки) времени, в течение которого в музее одновременно находилось максимальное число посетителей. Рассмотрим какой-нибудь такой промежуток. Его концами, очевидно, являются концевые точки каких-то двух отрезков. В решении задачи 8 (Дихотомия и поиск) в переменной С храниться количество отрезков, пересекающихся в текущей концевой точке. Сначала мы найдем Cmax - максимальную величину переменной C, затем определим, каким промежуткам соответствует максимальное количество посетителей в музее: {смысл массива A см. в задаче 8 (Дихотомия и поиск)} {находим Cmax} i:=1; Cmax:=0; пока (i<=2*N) и повторять если A[2,i]>0 то C:=C+1; Cmax:=max(Cmax, C); конец_то иначе C:=C-1; конец_иначе i:=i+1; конец_пока если Сmax=0, то посетителей не было вообще. Стоп. {ищем и печатаем промежутки с максимальным числом посетителей} i:=1; пока (i<=2*N) и повторять если A[2,i]>0 то C:=C+1; если С=Смах {это начало искомого промежутка?} то печатаем координату начала промежутка A[1,i] конец_то конец_то иначе если С=Смах {промежуток закончился} то печатаем координату конца промежутка A[1,i] конец_то C:=C-1; конец_иначе i:=i+1; конец_пока

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017