Naravno k-smerno zlivanje
Pri urejanju z zlivanjem problem najprej razbijemo na podprobleme velikosti 1, nato pa podprobleme po parih zlivamo v urejeno zaporedje. Vendar se v naravnih podatkih pogosto pojavijo naraščajoča podzaporedja, kar lahko s pridom izkoristimo pri pospešitvi algoritma. Pri naravnem zlivanju v zaporedju najprej poiščemo urejena podzaporedja, kjer si elementi sledijo v nepadajočem vrstnem redu - čete. Nato čete po skupinah združujemo - zlivamo tako, da z začetkov čet zaporedoma pobiramo najmanjše elemente.
Simuliraj
algoritem zunanjega urejanja z naravnim k-smernim zlivanjem.
Podano je zaporedje z $N$ elementi $x_i$, število čet $K$, ki jih sočasno
zlivamo, in število korakov $A$. Izpiši zaporedje po $A$ korakih. Če se je zaporedje urejeno prej, kot po $A$ korakih, postopek zaključi.
Omejitve podatkov:
- $1 \leq N \leq 10^5$
- $2 \leq K \leq 10$
- $1 \leq A \leq 20$
- $0 \leq x_i \leq 10^9$
Vhodni in izhodni podatki:
V prvi vrstici so podani število podatkov $N$, število čet $K$, ki jih sočasno zlivamo in število korakov $A$. Sledi $N$ vrstic, kjer $i$-ta vrstica opisuje $i$-ti podatek $x_i$. Po vrsticah izpiši zaporedje po $A$ korakih zlivanja.
Primer vhoda:
25 3 2
13
18
7
8
17
3
16
9
10
11
11
0
2
19
14
5
6
15
4
5
12
3
18
1
3
Pravilen izhod:
0
2
3
3
4
5
5
6
7
8
9
10
11
11
12
13
14
15
16
17
18
18
19
1
3
Postopek za zgornji primer $N=25$, $K=3$ in $A=2$:
V zaporedju na sliki najdemo 10 čet.
V fazi zlivanja nato združujemo po 3 zaporedne čete tako, da zaporedno z začetkov čet izbiramo najmanjše elemente:
Nato nadaljujemo z drugo skupino $K$ čet, ...,
dokler nam čet ne zmanjka. Po prvem koraku zlivanja, bo zgornje zaporedje izgledalo tako (barve označujejo četo iz katere smo dobili določen element):
V drugem koraku nam ostanejo še štiri čete