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

1 – ээс n хүртэлх бүхэл тоонуудаас бүрдсэн эрэмблэгдээгүй хүснэгт өгөгдөнө. Тоо давхцахгүй.

Дурын ялгаатай 2 тоог хооронд нь сольж болно.  Солих боломж нь хязгаарлагдмал байна.

Хязгаарласан тооноос хэтрүүлэлгүйгээр солих үйдэл хийхэд  үүсэх хамгийн том лексикографын ( lexicographical ) утгын хүснэгтийг тодорхойл.

Жишээ нь:

Arr = [1, 2, 3, 4], солих үйлдлийн тоо ихдээ  k = 1 гэвэл дараах хүснэгтүүд  1 удаа солих үйлдлээр бий  болно.

[2, 1, 3, 4]

[3, 2, 1, 4]

[4, 2, 3, 1]

Дээрх 4 хүснэгтийн ( үндсэн хүснэгтээ оруулаад ) хамгийн том утга нь [4,2,3,1].

Хэрэв k >= 2 гэвэл ахин нэг удаа солих үйлдэл  хийснээр хамгийн их боломжит утга нь [4, 3, 2, 1] болно.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо n, k өгөгдөнө.

n хүснэгтийн урт, k солих үйлдлийн тоо.

2 дахь мөрөнд зайгаар тусгаарлагдсан, давхцалгүй n тоо өгөгдөнө.

arr[i], үүнд: 1 <= arr[i]  <= n.

Хязгаарлалт

Хамгийн ихдээ к тооны солих үйлдлээр гарган авч болох лексикографын хамгийн том утгыг хэвлэ.

Жишээ

Оролт 1

5 1

4 2 3 5 1

Гаралт 1

5 2 3 4 1

Тайлбар 1

Оролтын хүснэгт [4, 2, 3, 5, 1] дахь 2 элементийн байрыг солиход  хамгийн том утга нь [5, 2, 3, 4, 1] болно.

Оролт 2

3 1

2 1 3

Гаралт 2

3 1 2

Тайлбар 2

1 солих үйлдлээр [1, 2, 3], [3, 1, 2] болон [2, 3, 1] -г гарган авч болно. Үүнээс [3, 1, 2] нь хамгийн том утга болно.

Оролт 3

2 1

2 1

Гаралт 3

2 1

Тайлбар 3

[2, 1] нь угаасаа хамгийн том утга.  Иймээс ямар нэг солих үйлдэл хэрэггүй.

Орчуулсан : Б.Баясгалантөгөлдөр АНУ