Skip to content

Latest commit

 

History

History
175 lines (114 loc) · 12.6 KB

mergesort.md

File metadata and controls

175 lines (114 loc) · 12.6 KB
Raw

Два указателя, сортировка слиянием

Количество пар с разницей, больше чем K

Найти количество пар элементов $a$ и $b$ в отсортированном массиве, такие что $b - a > K$.

Наивное решение: бинарный поиск. Будем считать, что массив уже отсортирован. Для каждого элемента $a$ найдем первый справа элемент $b$, который входит в ответ в паре с $a$. Нетрудно заметить, что все элементы, большие $b$, также входят в ответ. Итоговая асимптотика $O(n\log n)$.

А можно ли быстрее?

Да, давайте перебирать два указателя — два индекса $first$ и $second$. Будем перебирать $first$ просто слева направо и поддерживать для каждого $first$ первый элемент справа от него, такой что $a[second] - a[first] > K$ как $second$. Тогда в пару к $a=a[first]$ подходят ровно $n-second$ элементов массив начиная с $second$.

int second = 0, ans = 0;
for (int first = 0; first < n; ++first) {
    while (second != n && a[second] - a[first] <= r) {
        second++;
    }
    
    ans += n - second;
}

За сколько же работает это решение? С виду может показаться, что за $O(n^2)$, но давайте посмотрим сколько раз меняется значение переменной $second$. Так как оно изначально равняется нулю, только увеличивается и не может превысить $n$, то суммарно операций мы сделаем $O(n)$.

Это называется метод двух указателей — так как мы двигаем два указателя first и second одновременно слева направо по каким-то правилам. Обычно его используют на одном отсортированном массиве.

Давайте разберем еще примеры.

Максимальная разница, но не больше K

Найти в отсортированном массиве два числа $a$ и $b$ такие, что $b - a \leq K$, и при этом $b-a$ максимально.

Давайте просто переберем $first$ слева направо как указатель на $a$, и будем поддерживать $second$ как указатель на максимальный такой индекс, что $a[second] - a[first]\leq K$. Для этого достаточно просто после каждого сдвига $first$ на один сдвигать $second$ вправо, пока это условие не перестанет выполняться.

Заметим, что таким образом мы перебрем все пары $a$ и $b$, такие что $b - a \leq K$, и их при этом нельзя увеличить вправо (иначе мы бы увеличили). Очевидно, максимальная разница лежит именно в одной из такой пар, так что мы ее найдем.

Три массива

Чаще всего метод двух указателей применяют к одному отсортированному массиву. Но иногда можно применить его и на несколько, например, три массива.

Найти в трех отсортированных массивах элементы $a_i$, $b_j$ и $c_k$ такие, что $|\max(a_i, b_j, c_k) - \min(a_i, b_j, c_k)|$ минимально.

Для этого достаточно перебирать указатель $first$ на первый массив, $second$ на второй массив и $third$ на третий массив. Давайте теперь медленно увеличивать минимум из этих трех элементов так, чтобы максимум увеличился как можно меньше.

Изначально все указатели указывают на индекс $0$. После этого надо один из указателей сдвинуть направо. Какой? Тот, который указывает на минимальный из элементов. Почему? Если сдвинуть любой другой, то максимум возрастет, а минимум нет, такие комбинации вообще рассматривать бесполезно.

Так что мы просто сдвигаем каждый раз указатель на минимум из трех элементов, если есть куда его двигать, иначе заканчиваем. Каждый раз обновляем ответ. Так мы переберем всех разумные тройки элементов.

Слияние

Еще пример двух указателей на нескольких массивах.

Пусть у нас есть два отсортированных по неубыванию массива размера $n$ и $m$. Хотим получить отсортированный массив размера $n + m$ из исходных.

Пусть первый указатель будет указывать на начало первого массива, а второй, соответственно, на начало второго. Из двух текущих элементов, на которые указывают указатели, выберем наименьший и положим на соответствующую позицию в новом массиве, после чего сдвинем указатель. Продолжим этот процесс пока в обоих массивах не закончатся элементы. Тогда код будет выглядеть следующим образом:

int a[n + 1], b[m + 1], res[n + m];

a[n] = INF; // Создаем в конце массива фиктивный элемент, который заведомо больше остальных
b[m] = INF; // Чтобы избежать лишних случаев

for (int i = 0; i < n; ++i) {
    cin >> a[i];
}

for (int j = 0; j < m; ++j) {
    cin >> a[j];
}

int i = 0, j = 0;
for (int k = 0; k < n + m; ++k) {
    if (a[i] < b[j]) {
        res[k] = a[i];
        i++;
    } else {
        res[k] = b[j];
        j++;
    }
}

Итоговая асимптотика: $O(n + m)$.

Сортировка слиянием

Давайте подробно опишем как использовать операцию слияния для сортировки за $O(n\log n)$.

Пусть у нас есть какой-то массив.

int a[8] = {7, 2, 5, 6, 1, 3, 4, 8};

Сделаем такое предположение. Пусть мы уже умеем как-то сортировать массив размера $n$. Тогда научимся сортировать массив размера $2n$. Давайте разобьем наш массив на две половины, отсортируем каждую из них, а после это сделаем слияние двух массивов, которое мы научились делать за $O(n)$ в данных условиях. Также заметим, что массив размера $1$ уже отсортирован, тогда мы можем делать это процедуру рекурсивно. Тогда для данного массива $a$ это будет выглядеть следующим образом:

// (7 2 5 6 1 3 4 8)
// (7 2 5 6) (1 3 4 8)
// (7 2) (5 6) (1 3) (4 8)
// (2 7) (5 6) (1 3) (4 8)
// (2 5 6 7) (1 3 4 8)
// (1 2 3 4 5 6 7 8)

#include <algorithm> // Воспользуемся встроенной функцией merge

void merge_sort(vector<int> &v, int l, int r) { // v - вектор, который хотим отсортировать
    if (r - l == 1) {                            // l и r - полуинтервал, который хотим отсортировать
        return;
    }
    
    int mid = (l + r) / 2;
    merge_sort(v, l, mid);
    merge_sort(v, mid, r);
    vector<int> temp(r - l); // временный вектор
    merge(v.begin() + l, v.begin() + mid, v.begin() + mid, v.begin() + r, c.begin());
    for (int i = 0; i < r - l; ++i) {
        v[i + l] = temp[i];
    }
    return;
}

Так сколько же работает это решение?

Пускай $T(n)$ — время сортировки массива длины $n$, тогда для сортировки слиянием справедливо $T(n)=2T(n/2)+O(n)$ $O(n)$ — время, необходимое на то, чтобы слить два массива длины n. Распишем это соотношение:

$T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\ldots=T(1)+\log(n)O(n)=O(n\log(n)).$

Количество инверсий

Пусть у нас есть некоторая перестановка $a$. Инверсией называется пара индексов $i$ и $j$ такая, что $i &lt; j$ и $a[i] &gt; a[j]$.

Найти количество инверсий в данной перестановке.

Очевидно, что эта задача легко решается обычным перебором двух индексов за $O(n^2)$:

int a[n], ans = 0;

for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
        if (a[i] > a[j]) {
            ans++;
        }
    }
}

cout << ans << endl;

Внезапно эту задачу можно решить используя сортировку слиянием, слегка модифицируя её. Оставим ту же идею. Пусть мы умеем находить количество инверсий в массиве размера $n$, научимся находить количество инверсий в массиве размера $2n$.

Заметим, что мы уже знаем количество инверсий в левой половине и в правой половине массива. Осталось лишь посчитать число инверсий, где одно число лежит в левой половине, а второе в правой половине. Как же их посчитать?

Давайте подробнее рассмотрим операцию merge левой и правой половины (которую мы ранее заменили на вызов встроенной функции merge). Первый указатель указывает на элемент левой половины, второй указатель указывает на элемент второй половины, мы смотрим на минимум из них и этот указатель вдигаем вправо.

Рассмотрим число $A$ в левой половине. В скольки инверсиях между половинами оно участвует? В стольки, сколько чисел в правой половине меньше, чем оно. Знаем ли мы это количество? Да! Ровно в тот момент, когда мы число $A$ вносим в слитый массив, второй указатель указывает на первое число в правой половине, которое больше чем $A$.

Значит в тот момент, когда мы добавляем число $A$ из левой половины, к ответу достаточно прибавить индекс второго указателя (минус начало правой половины). Так мы учтем все инверсии между половинами.

Задание

Решите как можно больше задач из теоретического контеста https://informatics.msk.ru/mod/statements/view3.php?id=38944

Решите как можно больше задач практического контеста https://codeforces.com/group/g92L0id9Yb/contest/236738