ABC414D

問題

ABC414D

解法

$M=1$ の場合

簡単のため，$M = 1$ で考える．
基地を設置するベストな場所は，左端の家と右端の家の中点となり，一意に定まる．

$M \geq 1$ の場合

次に，$N$ 個の点を $M$ 個のブロックに分ける．
ブロックごとに，基地のベストな位置は一意に定まる．
これは $M=1$ のときの様に，ブロック毎の中点に定まる．

後は，どの様にブロックに分割するのが最適かを考える．
$M$個のブロックに分ける事は，$M-1$個の仕切りを入れる事と同一視出来る．
仕切りの部分は，電波が届かなくてよいから，家と家の間の距離が大きいほうから $M-1$ 個を仕切りとして選べば最適．

コード

main.cpp

int main() {
  ll n, m;
  cin >> n >> m;
  vll a(n); rep(i,n) { cin >> a[i]; }
  sort(all(a));

  ll s = 0;
  vll diff;
  rep(i,n-1){
    diff.push_back(a[i+1] - a[i]);
    s += a[i+1] - a[i];
  }
  sort(rall(diff));

  rep(i,m-1){// rem: m-1
    s -= diff[i];
  }
  cout << s << endl;

  return 0;
}