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