クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「3-1 Aggressive cows（POJ No.2456）」(p.131)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「3-1 Aggressive cows（POJ No.2456）」(p.131)
のコードをPythonで書き直したものとなっています。

入力


N\,M\\x_1\,…\,x_N

入力例



5 3
1 2 8 4 9


解答

INF = 10 ** 9 + 1

# 入力
N, M = map(int,input().split())
x = list(map(int,input().split()))

# 条件を満たすか判定
def C(d):
    last = 0
    for i in range(1, M):
        crt = last + 1
        while crt < N and x[crt] - x[last] < d:
            crt += 1
        if crt == N:
            return False
        last = crt
    return True

# はじめにxをソートしておく
x.sort()

# 解の存在範囲を初期化
lb = 0
ub = INF

while ub - lb > 1:
    mid = (lb + ub) // 2
    if C(mid):
        lb = mid
    else:
        ub = mid

print(lb)