ルータのインストール(2110)

Binary Search

質問する

道現家のN個は垂直線上にあります.各家の座標はx 1,...,xNで、家には同じ座標が複数ありません.
道賢はいつでもどこでもWiFiを楽しむために、家にC個のルーターを設置する予定だ.WiFiはできるだけ多くの場所で使用するため、1世帯に1つのルータしかインストールできず、最も隣接する2つのルータ間の距離をできるだけ大きくしなければならない.
N世帯にC個のルータを適切にインストールし,2個の最も近いルータ間の距離を最大にするプログラムを作成する.

入力

最初の行では、家の個数N(2≦N≦200000)とルータの個数C(2≦C≦N)との間に1つ以上のスペースがある.2行目からN行目では、1行につき家屋座標を表すxi(1≦xi≦10000000)が1つずつ表示される.

しゅつりょく

1行目に最も近い2つのルータ間の最大距離を出力します.

ヒント

1、4、8または1、4、9にルータを設置する場合、最も隣接する2つのルータ間の距離は3であり、3つのルータを設置することはできず、3つのルータを設置することはできない.

import sys

N, C = map(int, sys.stdin.readline().split()) 
ap = [int(sys.stdin.readline()) for _ in range(N)] 
ap.sort() 
answer = 0

def solve(minimum, maximum):

    if minimum > maximum: 
        return 
    dist = (maximum + minimum) // 2 
    cnt = 1 
    target = 0 
    
    for idx in range(N):
        if ap[idx] >= ap[target] + dist:
            cnt += 1
            target = idx
            
    if cnt >= C:
        global answer
        answer = max(answer, dist) 
        solve(dist + 1, maximum) 
    else:
        solve(minimum, dist - 1)
        
solve(1, (ap[-1] - ap[0])//(C - 1) + 1) 
print(str(answer))

参照)
https://suri78.tistory.com/86