最大値の最小化 および 最小値の最大化 のような形の問題には、 二分探索 が適用できることがしばしばあります。本問も例外ではありません。

答え \(t\) を決め打ちます。このとき、ひとつの避難所で座標 \(x,x+1,\dots,x+t\) の住民を受け入れることができます(避難所を \((2x+t)/2\) に設置すればよいです)。

• 住民を座標 \(x\) の昇順に調べる。
  • もし今の住民が既存の避難所にカバーされている場合、その避難所を使えばよいです。
  • そうでない場合、住民を座標の昇順に調べているため、座標 \(x,x+1,\dots,x+t\) にいる住民をカバーするような避難所を設置するのが最善です。

こうして、避難所が \(K\) 個以内で済めば答えは \(t\) 以下、そうでなければ答えは \(t+1\) 以上です。

あとは、 \(t\) を二分探索すればよいです。
時間計算量は \(O(N \log (\max X))\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,K;
  cin >> N >> K;
  vector<int> X(N);
  for(auto &nx : X){cin >> nx;}
  int l=0,r=X[N-1]-X[0];
  while(l<=r){
    int te=(l+r)/2;
    int cnt=1,lef=X[0];
    for(int i=1;i<N;i++){
      if((X[i]-lef)>te){
        cnt++;
        lef=X[i];
      }
    }
    if(cnt>K){l=te+1;}
    else{r=te-1;}
  }
  cout << l << "\n";
  return 0;
}