[ラーニングテストエンコーディング]ルータのインストール

ソース:https://www.acmicpc.net/problem/2110

もんだいぶんせき

まず時間制限は2秒です.でもNは2万0したがって,Nlognの複雑さで実装する必要があることに気づくかもしれない.もちろん、このタイプの人は、このような探求で国策をしています.
しかし、まず問題を説明するのは容易ではない.2つのルータ間の距離を最大限に近づける...?この問題を読んで、私の気持ちは本当に下の図のようです...

この絵ほど私の気持ちを代表するものはない...
やはり問題を分析するのか疑わしい私が聞いた疑念はこうだった.

彼が探索する必要があるのは知っていますが、midを設置してもmidほど短い間隔はないでしょう...?どうすればいいの?

start、endを調整する条件は何ですか?茫然としている.

実は上に書いてある悩みの何倍も.結局私はこのような結論を出した.

まず前の家からルーターを取り付けましょう真ん中に落ちないこともあるけど落ちてくれればいいんだそうじゃなくてもそのまま行こう

でもこんな疑問もあります.
真ん中から登場したらどうしますか?
しかし、最初の家から真ん中までの距離があまり近くない場合、2番目の家の間隔がmidより大きい場合は、上記のように行っても問題ありません!
このような考えでコードを整理してみましょう.コードを確認!

コードをチェックしてみましょう。

import sys

# 2110번 문제
input = sys.stdin.readline

N, C = map(int, input().split())
coordinate_list = []

for _ in range(N):
    coordinate_list.append(int(input()))
    
coordinate_list = sorted(coordinate_list) # 정렬

start, end = 1, coordinate_list[N - 1] - coordinate_list[0]

# 탐색 시작
while start <= end:
    mid = (start + end) // 2
    count = 1
    current_house = coordinate_list[0]
    
    # 앞집에서 부터 공유기 심기
    for i in range(1, N):
        if coordinate_list[i] - current_house >= mid:
            count += 1
            current_house = coordinate_list[i]
            
    if count >= C:
        start = mid + 1
    else:
        end = mid - 1

print(end)

まず入力したリストを整理します.前の家からルーターを設置することにしたからです.
そしてstartは1、endは最初の家と最後の家の距離差です.そして、この探索では、最初の家からルーターを敷き詰めます.

    mid = (start + end) // 2
    count = 1
    current_house = coordinate_list[0]

まず、基本的なアイデアは前の家からルーターを取り付け、Cサイズの家にルーターを取り付けることですか?チェックするだけです.うまく敷けないのは、幅が広すぎるから、敷けるならもう少し広くても大丈夫という意味!

    # 앞집에서 부터 공유기 심기
    for i in range(1, N):
        if coordinate_list[i] - current_house >= mid:
            count += 1
            current_house = coordinate_list[i]

current houseは、以前ルータを栽培していた家の座標を格納しています.すなわち,座標リストをブラウズする際に,間隔がmidより大きいかどうかをチェックし,条件を満たすとルータを植え込む.
ルーターを植え終わったら、Cの条件に合わせてstart、endを調整できます.
最後に、endを出力して、問題はすべて解決しました!