4.3. Применения сортировки

  •  
      4.3.1. Найти количество различных чисел среди элементов данного массива. Число действий порядка n*log n. (Эта задача уже была в главе о массивах.)

      Решение. Отсортировать числа, а затем посчитать количество различных, просматривая элементы массива по порядку.

      4.3.2. Дано n отрезков [a[i], b[i]] на прямой (i=1..n). Найти максимальное k, для которого существует точка прямой, покрытая k отрезками ("максимальное число слоев"). Число действий - порядка n*log n.

      Решение. Упорядочим все левые и правые концы отрезков вместе (при этом левый конец считается меньше правого конца, расположенного в той же точке прямой). Далее двигаемся слева направо, считая число слоев. Встреченный левый конец увеличивает число слоев на 1, правый - уменьшает. Отметим, что примыкающие друг к другу отрезки обрабатываются правильно: сначала идет левый конец (правого отрезка), а затем - правый (левого отрезка).

      4.3.3. Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Число действий порядка n*log n.

      Решение. Упорядочим точки по x-координате, а при равных x-координатах - по y-координате. В таком порядке и можно проводить ломаную.

      4.3.4. Та же задача, если ломаная должна быть замкнутой.

      Решение. Возьмем самую левую точку (т.е. точку с наименьшей x-координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи снизу вверх, а точки на одном луче упорядочим по расстоянию от начала луча (это делается для всех лучей, кроме нижнего и верхнего). Ломаная выходит из выбранной (самой левой) точки по нижнему лучу, затем по всем остальным лучам (в описанном порядке) и возвращается по верхнему лучу.

      4.3.5. Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Резиновое колечко, натянутое на вдитые в доску гвозди - их выпуклая оболочка.) Число операций не более n*log n.

      Указание. Упорядочим точки - годится любой из порядков, использованных в двух предыдущих задачах. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек. (Для хранения выпуклой оболочки полезно использовать дек, см. главу 6 о типах данных. Впрочем, при упорядочении точек по углам это излишне.)

Другие записи

10.06.2016. 4.1. Квадратичные алгоритмы
  4.1.1. Пусть a[1], ..., a[n] - целые числа. Требуется построить массив b[1], ..., b[n], содержащий те же числа, для которого b[1] <= ... <= b[n]. Замечание. Среди чисел a[1]...a[n] могут быть…
10.06.2016. 4.4. Нижние оценки для числа сравнений при сортировке
  Пусть имеется n различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем доступ к функции…
10.06.2016. 4.5. Родственные сортировке задачи
  4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого легкого из n камней? Решение. Очевидный алгоритм с инвариантом "найден самый легкий камень…