АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Танд 1-ээс n хүртэл дугаарлагдсан өсөх дараалал байдаг [1,2,3, ….., n].

Гэвч тухайн дараалал нь эмх замбраагүй болчихож. Та 2 тооны байр солих үйлдэл ашиглан тухайн дарааллыг хамгийн цөөн үйлдлээр өсөхөөр эрэмбэлэх юм. Жишээ нь :

n=7, arr=[7,1,3,2,4,5,6] үед

0 [7,1,3,2,4,5,6] swap(0,3)

1 [2,1,3,7,4,5,6] swap(0,1)

2 [1,2,3,7,4,5,6] swap(3,4)

3 [1,2,3,4,7,5,6] swap(4,5)

4 [1,2,3,4,5,7,6] swap(5,6)

5 [1,2,3,4,5,6,7]

Үүнд нийт 5 удаа байр солих үйлдэл ашигласан.

Оролт:

Эхний мөрөнд дарааллын урт n. ( 1≤ n ≤ 10⁵ ) Бүхэл тоо.

Дараагийн мөрөнд  arr[i]  ( 1≤ arr[i] ≤ n). Бүхэл тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Гаралт:

Хамгийн цөөн Swap үйлдлийн тоо.

Жишээ:

Оролт:

4

4 3 1 2

Гаралт:

3

Тайлбар:

[4,3,1,2] -> [1,3,4,2] (swap (0,2) ) -> [1,4,3,2] (swap (1,2) ) -> [1,2,3,4] (swap(1,3) ) :

Жишээ 1:

Оролт:

5

2 3 4 1 5

Гаралт:

3

Тайлбар:

[2,3,4,1,5] -> [2,3,1,4,5] (swap(2,3) ) -> [3,2,1,4,5] (swap(0,1) ) -> [1,2,3,4,5] (swap(0,2) ) :

Жишээ 2:

Оролт:

7

1 3 5 2 4 6 7

Гаралт:

3

Тайлбар:

[1,3,5,2,4,6,7] -> [1,2,5,3,4,6,7] (swap(1,3) ) -> [1,2,3,5,4,6,7] (swap(2,3) ) -> [1,2,3,4,5,6,7] (swap(3,4) ) :

Орчуулсан  : Дархан-Уул аймгийн Союз сургуулийн 12-р ангийн сурагч Б.Сумьяабазар