### Problem Statement There are $N$ houses number...

思路说明（中文）

1. 将房屋坐标排序
   设排序后序列为 $x_1\le x_2\le\cdots\le x_N$。

2. “一条基站线”下的代价
   如果只有一座基站覆盖所有房屋，则最小信号强度为

   $$x_N-x_1$$

   ——把基站放在 $\tfrac{x_1+x_N}{2}$ 处即可。
   这是因为每段的信号强度 $s$ 对应的覆盖半径是 $\tfrac{s}{2}$， 要让最左与最右两栋房屋都被覆盖，半径至少是 $\tfrac{x_N-x_1}{2}$，从而 $s=x_N-x_1$。

3. 拆分成多段的收益
   若我们把序列在若干位置“断开”，每段的花费是
   $(\text{段右端坐标}-\text{段左端坐标})$。
   全部段花费之和 = $(x_N-x_1)$ 减去 每一次断开造成的“空隙”大小。
   记相邻房屋间的间隔

   $$d_i = x_{i+1}-x_i,\quad i=1..N-1.$$

   若要放置 $M$ 个基站，就能断开最多 $M-1$ 处，于是总花费为

   $$(x_N-x_1) \;-\; \text{选出的 }(M-1)\text{ 个最大 }d_i\text{ 的和}.$$

4. 算法步骤

   • 排序 $X$（$O(N\log N)$）。
   • 计算全部间隔 $d_i$（$O(N)$）。
   • 将 $d_i$ 按降序排序，取前 $M-1$ 个求和（$O(N\log N)$）。
   • 结果 = $(x_N-x_1) - \text{上述求和}$。
     当 $M\ge N$ 时可以让每栋房子独占一个基站且信号强度为 $0$，答案自然为 $0$。

5. 复杂度分析

   • 排序两次：整体 $O(N\log N)$。
   • 额外内存 $O(N)$。

cpp
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    if (!(cin >> N >> M)) return 0;
    
    vector<int64> x(N);
    for (int i = 0; i < N; ++i) cin >> x[i];
    sort(x.begin(), x.end());                 // 步骤 1
    
    if (M >= N) {                             // 特判：基站足够多
        cout << 0 << '\n';
        return 0;
    }
    
    vector<int64> gaps;
    gaps.reserve(N - 1);
    for (int i = 0; i < N - 1; ++i)           // 步骤 2
        gaps.push_back(x[i + 1] - x[i]);
    
    sort(gaps.rbegin(), gaps.rend());         // 步骤 3：降序
    
    int64 save = 0;                           // 可以节省的总空隙
    for (int i = 0; i < M - 1; ++i)
        save += gaps[i];
    
    int64 ans = (x.back() - x.front()) - save;// 步骤 4
    cout << ans << '\n';
    return 0;
}

解释小结

• 核心：把“覆盖所有房屋的一段”拆成若干段，节省的正是拆开的最大空隙。
• 答案：$(x_{\max}-x_{\min})-$“前 $M-1$ 大的相邻空隙之和”。
• 正确性：分段之间绝不会重叠，否则可收缩信号强度；段内最优就是让基站居中。
• 时间/空间：$O(N\log N)$ / $O(N)$，可轻松通过 $N\le5\times10^5$。