Module 1: Trie

БОР

Module 2: Sparse Table

Разреженная таблица

Module 3: Segment Tree

Дерево отрезков
Максимальная сумма подотрезка на заданном отрезке

Module 4: Segment Tree Lazy propagation

Segment Tree с Lazy Propagation

Module 5: More on trees

Euler порядок посещений вершин
DP на дереве (Tree DP)

Module 6: Binary jumping

Двоичные подъёмы (прыжки)
Наименьший общий предок

Module 7: Cyclic Games

Игры на циклических графах

Module 8: Divide & Conquer

Разделяй и властвуй

Module 9: SQRT Techniques

SQRT Декомпозиция
Корневые эвристики
Алгоритм Мо

Разделяй и властвуй - Preparation to IOI Part 4

Главная Курсы Ресурсы Задачи Национальная олимпиада Соревнования Таблица лидеров

...

Главная/Courses/Preparation to IOI Part 4/Module 8: Divide & Conquer/Разделяй и властвуй

Разделяй и властвуй

Разделяй и властвуй

Введение

Разделяй и властвуй — это алгоритмическая техника, в которой задача решается с помощью стратегии «Разделяй, властвуй и объединяй».

Типичный алгоритм «Разделяй и властвуй» решает задачу с помощью следующих трёх шагов:

Разделить: деление задачи на более мелкие подзадачи.
Властвовать: решение подзадач путём рекурсивного вызова до тех пор, пока они не будут решены.
Объединить: объединение подзадач для получения окончательного решения исходной задачи.

Применение

Условие задачи

Дан массив $a_1, a_2, \ldots, a_n$ из чисел. Требуется отсортировать массив за с помощью техники «Разделяй и властвуй».

n

O(NlogN)

Решение

Давайте реализуем функцию $sort(a)$ , которая получает на вход массив и возвращает отсортированный массив.

Если $n = 1$ , то возвращаем просто $a$ , так как массив из одного элемента отсортирован.
Если $n \ne 1$ . Пусть $m = \lfloor \frac{n}{2} \rfloor$ , поделим массив на 2 части $a[1 \ldots m]$ и $a[m+1 \ldots n]$ . Отсортируем эти части по отдельности, вызвав рекурсивно $sort(a[1 \ldots m])$ и $sort(a[m+1 \ldots n])$ . Запишем их результаты в $L$ и $R$ соответственно. Объединим 2 отсортированных массива в один за $O(|L| + |R|)$ и вернём результат.

Реализация

vector<int> sort(vector<int> a) {
    if (a.size() <= 1) {
        return a;
    }
    int m = a.size() / 2;

    vector<int> L = sort(vector<int>(a.begin(), a.begin() + m));
    vector<int> R = sort(vector<int>(a.begin() + m, a.end()));

    vector<int> res;
    merge(L.begin(), L.end(), R.begin(), R.end(), back_inserter(res));
    return res;
}