問題の言い換え

\(X\) を昇順にソートして，\(X_1 \leq X_2 \leq \dots \leq X_N\) であるとします．

基地局を座標 \(r\) に配置し，電波強度を \(x\) としたとき，電波が届く座標の範囲は \(r-\frac{x}{2}\) 以上 \(r + \frac{x}{2}\) 以下であり，その長さは \(x\) です．また，このなかにある家の番号は連続した範囲になっています．

家 \(l\) から家 \(r\) (\(l \leq r\)) までに電波が届くような基地局の電波強度 \(x\) の最小値は \((X_r - X_l)\) です．

よって，\(1, \dots, N\) を \(M\) 個の範囲に分割し，各範囲に対する \((X_r - X_l)\) の総和を最小化する問題に言い換えられます．

さらなる言い換え

ここで，隣り合う家の間隔 \(D_i := X_{i+1} - X_i\) (\(i = 1,\cdots,N-1\)) をおきます．これは，図における紫色の数値に対応します．このとき，

\[(X_r - X_l) = D_l + \dots + D_{r-1}\]

となることから，\(D_1, \dots, D_{N-1}\) のなかから \(M-1\) 個を選んで消し，残りの総和を最小化する問題に言い換えられます．

よって，\(D\) を昇順にソートして，冒頭の \(N-M\) 個の総和を求めれば答えになります．

実装例

数値のソートは，主要なプログラミング言語の多くにおいては標準ライブラリの関数として提供されており，それらを用いて簡潔に実装できます．

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <array>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::string;
using std::pair;
using std::vector;
using std::min;
using std::max;
using std::array;
#include <atcoder/all>

typedef long long int ll;

ll n, m;
vector<ll> x;

void solve () {
	sort(x.begin(), x.end());

	vector<ll> d;
	for (ll i = 0; i < n-1; i++) {
		d.push_back(x[i+1] - x[i]);
	}
	sort(d.begin(), d.end());

	ll ans = 0;
	for (ll i = 0; i < n-m; i++) {
		ans += d[i];
	}

	cout << ans << "\n";
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	x.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> x[i];
	}

	solve();

	return 0;
}