Использование сортировки.
| Во всех задачах, в условиях которых упомянуты массивы, если это не оговорено особо, размер вспомогательной памяти не должен зависеть от их длин, а число действий пропорционально их длинам. В задачах 1 – 7 массивы предполагаются отсортироваными. В задачах 8 – 12 число действий должно быть порядка n log n. |
Задачи
1.
Найти для массива x[1..n] число различных элементов (Число действий Cn)
2.
Найти для массивов x[1..n] и y[1..p] их пересечение, т.е. общие элементы с учетом кратности (Число действий Cn+p)
3.
Для массивов x[1..n], y[1..p] и z[1..q], найти первый общий элемент
- если он заведомо есть
- если этого заранее неизвестно.
4. (cлияние)
Объединить массивы x[1..n] и y[1..p] в z[1..n+p].
6.
Сумму вида x[i] + y[j] наиболее близкую к заданному числу a. (Число действий Cn+p; исходные массивы запрещено менять.)
7. (двоичный поиск)
В x[1..n] найти число заданное a. Число действий порядка log n
8.
Для массива x[1..n] найти наименьшее натуральное a, непредставимое в виде суммы каких-либо его элементов. Число действий порядка n log n.
9.
Дано n отрезков на прямой. Найти максимальное K (по всем точкам прямой) такое, что точка покрыта K слоями отрезков. Число действий порядка n log n
10.
Дано n точек на плоскости.
- Построить n-1-звенную несамопересекающуюся ломаную, проходящую через все эти точки. Число действий порядка n log n.
- То же, но ломаная n-звенная замкнутая.
11*.
Построить (при тех же ограничениях) выпуклую оболочку для n точек на плоскости.