Использование сортировки.
| Во всех задачах, в условиях которых упомянуты массивы, если это не оговорено особо, размер вспомогательной памяти не должен зависеть от их длин, а число действий пропорционально их длинам. В задачах 1 – 7 массивы предполагаются отсортироваными. В задачах 8 – 12 число действий должно быть порядка n log n. |
Найти для массива
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 точек на плоскости.