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

N ширхэг элементтэй А массив болон К тоо өгөгдөв. Чиний даалгавар бол А массиваас ямар нэгэн К ширхэг элементтэй дэд массивыг сонгон авч, тухайн дэд массивын хамгийн их болон хамгийн бага элементүүдийн ялгавар нь хамгийн бага байх тоог олох ёстой.

Жишээ нь

A=[1,4,7,2]  ба К=2 үед A’=[4,7] гэж дэд массивыг авбал  max(4,7)-min(4,7)=7-4=3 болно.  Харин бүх боломжит дэд массивууд дотроос A’=[1,2] гэж авбал max(1,2)-min(1,2)=2-1=1 хамгийн бага ялгавар болно.

Оролтын хэлбэр:

Эхний мөрөнд массивын элементүүдийн тоог илэрхийлэх N тоо

Хоёрдугаар мөрөнд К тоо

Дараагийн N ширхэг мөрд массивын элементүүд байрлана.

Хязгаарлалт:

2 <= n <= 10^5

2 <= k <= n

0 <= A[i] <= 10^9

Гаралтын хэлбэр: 

Сонгож авсан массивуудаас боломжит хамгийн бага зөрүү болох ганц тоог хэвлэнэ.

Жишээ Оролт 0

7

3

10

100

300

200

1000

20

30

Жишээ Гаралт 0

20

Тайлбар 0

[10, 20, 30] гэсэн дэд массивыг сонгож авахад

max(10,20,30) - min(10,20,30) = 30 - 10 = 20  хамгийн бага зөрүү олдсон байна.

Жишээ Оролт 1

10

4

1

2

3

4

10

20

30

40

100

200

Жишээ Гаралт 1

3

Тайлбар 1

Энд [1, 2, 3, 4] гэсэн дэд массивыг сонгож авахад

max(1,2,3,4) - min(1,2,3,4) = 4 - 1 = 3 буюу хамгйин бага утга нь олдож байна.

Жишээ Оролт 2

5

2

1

2

1

2

1

Жишээ Гаралт 2

0

Тайлбар 2

Энд [1,1] эсвэл [2,2] гэж сонгож авбал хамгийн бага зөрүү нь 0 болно.

Орчуулсан : Хөвсгөл аймгийн Ирээдүй сургуулийн багш Д.Батмөнх