Unfairness

صورت مسأله: با در اختیار داشتن یک آرایه n عددی، k عدد از بین آن ها طوری انتخاب کنید به طوری که بی عدالتی به حداقل برسد. سپس مقدار بی عدالتی را به عنوان خروجی نمایش دهید.

تعریف بی عدالتی: اختلاف بزرگترین عدد از کوچکترین عدد در مجموعه k

n اندازه کل مجموعه  اعداد و k تعداد اعداد انتخابی را نشان می دهد، مثال:

ورودی :

۷

۳

۱۲۳

۴۳

۱۲۵

۱۴۰

۴۲

۶۰

۶۱

 

خروجی:

۱۷

 

توضیح: در مجموعه داده شده، مجموعه ۳ تایی (۱۲۳و ۱۲۵ و ۱۴۰) دارای کمترین بی عدالتی یعنی ۱۷ هستند که از تفاضل ۱۴۰ و ۱۲۳ به دست آمده است.

در کدنویسی الگوریتمی راه حل، نکته اصلی مرتب سازی اعداد و سپس کنترل مجموعه های k تایی به صورت افزایشی است.

 

---

n = input()
k = input()
candies = [input() for i in range(0, n)]
candies.sort()
c = 0
unfairness = 10**10

for i in candies :
    diff = candies[c + k - 1] - candies[c]
    if diff < unfairness :
        unfairness = diff
    if c + k == len(candies) :
        break
    c += 1

print unfairness