Вход


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

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

  


Номер 9


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


Задача 9. На прямой окрасили N отрезков.Известны координата L[I] левого конца отрезка и координата R[I] правого конца I-го отрезка для I=1, ..., N. Найти сумму длин всех окрашенных частей прямой. Примечание. Число N столь велико, что на выполнение N*N даже простейших операций не хватит времени. МОДИФИКАЦИЯ. На окружности окрасили N дуг. Известны угловая координата L[I] начала и R[I] конца I-ой дуги (от начала к концу двигались, закрашивая дугу, против часовой стрелки). Какая доля окружности окрашена?

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


Решение задачи 9. Будем моделировать закрашивание этих N отрезков. Достаточно отсортировать отрезки в порядке неубывания координат левых концов. После этого осуществляется простой просмотр упорядоченных отрезков с анализом следующих возможных ситуаций: 1. Если текущий отрезок пересекается с закрашиваемым отрезком (его левая координата не больше правого конца закрашиваемого отрезка), то новым правым концом закрашиваемого сейчас отрезка становится более правый из концов закрашиваемого и текущего отрезков. 2. Если текущий отрезок не пересекается с закрашиваемым отрезком, то закраска предыдущего отрезка закончена, его длина суммируется с длиной уже закрашенной части, а закрашиваемым отрезком становится текущий отрезок. Процесс продолжается до тех пор, пока не будут просмотрены все отрезки. После этого длина последнего закрашенного отрезка суммируется с длиной ранее закрашенной части.

Назад



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

  


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