[伯俊]ルータ設置2110回

リンク:https://www.acmicpc.net/problem/2110
🙄 質問する
道現家のN個は垂直線上にあります.どの家の座標もx 1、x 2、...xn、同じ座標を持つ家具は複数ありません.
いつでもどこでもWiFiを楽しむために、道賢は家にC個のルーターを設置しようとした.WiFiをできるだけ多くの場所で利用したいので、1つの家庭に1つのルータしか設置しないで、できるだけ隣接する2つのルータ間の距離を広げたいと思っています.
N世帯にC個のルータを適切にインストールし,2個の最も近いルータ間の距離を最大にするプログラムを作成する.입력 조건

の最初の行では、家屋数N(2<=N<=20000)とルータ数C(2<=C<=N)との間に1つ以上のスペースがある.

の2行目からN行目のxi(1<=xi<=100000)は家屋の座標を表す.

출력 조건

は、1行目に最も近い2つのルータ間の最大距離

を出力する. 입력 예시

5 3
1
2
8
4
9

출력 예시

3

힌트1、4、8または1、4、9にルータを取り付けると、最も隣接する2つのルータ間の距離は3であり、3つのルータを取り付けることができず、この距離よりも大きい距離になります.
😁 に答える