마구간 정하기(결정알고리즘)

 N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마 구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요.

 

import sys
# sys.stdin=open("input.txt","rt")
n,m = map(int,input().split())
# n = int(input())
# arr = list(map(int,input().split()))
# n = input()
# arr = [list(map(int,input().split())) for _ in range(n)]
arr = [int(input()) for _ in range(n)]

arr = sorted(arr)

lt = 1
rt = max(arr)

res = 0

while lt <= rt:
    mid = (lt+rt) //2
    a = 1
    cnt = 1
    for i in arr:
        if mid <= i - a:
            cnt+=1
            a = i
  
    if m <= cnt:
        res = mid
        lt = mid +1
    else:
        rt = mid -1



print(res)