Bo‘l va boshqar - Course 4

Modul 1: Trie

Trie

Modul 2: Sparse Table

Sparse table

Modul 3: Oraliqlar daraxti

Oralilar daraxti
Berilgan oraliqda eng katta qism oraliq yig‘indisi

Modul 4: Oraliqlar daraxtida erinchoq yangilanishlar

Oraliqlar daraxtida erinchoq yangilashlar

Modul 6: Daraxtlarga oid texnikalar

Eyler sayri - cho‘qqilarga tashrif buyurish tartibi
Daraxtda DP (Tree DP)

Modul 5: Ikkilik sakrashlar

Ikkilik ko‘tarilishlar (sakrashlar)
Eng kichik umumiy ajdod

Modul 8: Sikllik o'yinlar

Siklik graflarda o‘yinlar

Modul 8: Bo'l va Boshqar

Bo‘l va boshqar

Module 9: SQRT texnikalar

SQRT dekompozitsiyasi
Ildiz evristikalari
Mo algoritmi

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Courses/Course 4/Modul 8: Bo'l va Boshqar/Bo‘l va boshqar

Bo‘l va boshqar

Bo‘l va boshqar

Kirish

Bo‘lib boshqar — bu algoritmik texnika bo‘lib, unda masala «Bo‘l, boshqar va birlashtir» strategiyasi yordamida yechiladi.

Odatdagi «Bo‘lib boshqar» algoritmi masalani quyidagi uchta qadam yordamida yechadi:

Bo‘lish: masalani kichikroq kichik masalalarga bo‘lish.
Boshqarish: kichik masalalarni rekursiv chaqirish orqali, ular yechilguncha yechish.
Birlashtirish: kichik masalalarni birlashtirib, boshlang‘ich masalaning yakuniy yechimini olish.

Qo‘llash

Masala sharti

$n$ ta sonlardan iborat $a_1, a_2, \ldots, a_n$ massivi berilgan. «Bo‘lib boshqar» texnikasi yordamida massivni da saralash talab etiladi.

n

O(NlogN)

Yechim

Keling, kirishda massivni qabul qilib, saralangan massivni qaytaradigan $sort(a)$ funksiyasini amalga oshiraylik.

Agar $n = 1$ bo‘lsa, shunchaki $a$ ni qaytaramiz, chunki bitta elementli massiv saralangan bo‘ladi.
Agar $n \ne 1$ bo‘lsa. $m = \lfloor \frac{n}{2} \rfloor$ bo‘lsin, massivni 2 qismga $a[1 \ldots m]$ va $a[m+1 \ldots n]$ ga bo‘lamiz. Bu qismlarni alohida saralaymiz, rekursiv ravishda $sort(a[1 \ldots m])$ va $sort(a[m+1 \ldots n])$ ni chaqiramiz. Ularning natijalarini mos ravishda $L$ va $R$ ga yozamiz. 2 ta saralangan massivni $O(|L| + |R|)$ da bittaga birlashtiramiz va natijani qaytaramiz.

Amalga oshirish

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;
}