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

To minimize the total signal strength, observe that each base‐station of strength $x$ covers an interval of length $x$. Since you have $M$ intervals to cover all $N$ house‐points, you want to partition the sorted list of house coordinates into $M$ contiguous groups so as to minimize the sum of the spans of those groups.

1. Sort the house coordinates: $$X_{(1)} \le X_{(2)} \le \cdots \le X_{(N)}.$$
2. Compute the gaps between adjacent houses: $$d_i = X_{(i+1)} - X_{(i)}, \quad i = 1,2,\dots,N-1.$$
3. If you only place one base station ($M=1$), you must cover from $X_{(1)}$ to $X_{(N)}$, so the total strength is $$X_{(N)} - X_{(1)}.$$
4. For $M>1$, you can “break” the line at the $M-1$ largest gaps, effectively creating $M$ segments. Within each segment $[L,R]$ you need strength $R-L$. Hence the minimum total strength is $$\bigl(X_{(N)} - X_{(1)}\bigr)\;-\;\sum_{\substack{\text{the }(M-1)\\\text{largest }d_i}} d_i.$$ Equivalently, $$\text{answer} = \sum_{i=1}^{N-1} d_i \;-\;\sum_{\substack{\text{the }(M-1)\\\text{largest }d_i}} d_i = \sum_{\substack{\text{the smallest }(N-M)\\\text{gaps among }d_i}} d_i.$$

Algorithmic steps in $O(N\log N)$ time:

text
1. Read N, M and array X of length N.
2. Sort X.
3. Build array D of length N−1 with D[i] = X[i+1] − X[i].
4. Sort D in descending order.
5. Sum up D[M], D[M+1], …, D[N−1] (i.e. skip the largest M−1 gaps).
   That sum is your answer.

• If $M\ge N$, you can station one transmitter per house (or even more), so each house lies exactly at a station: answer = 0.
• If $M=1$, you get a single interval covering all houses: answer = $\max X_i - \min X_i$.

This greedy “break at the largest gaps” is optimal because any reduction in total covered length comes precisely from not spanning the largest empty stretches between houses.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<ll> X(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i];
    }

    if (M >= N) {
        // We can place at least one station per house
        cout << 0 << "\n";
        return 0;
    }

    sort(X.begin(), X.end());

    // Compute gaps between consecutive houses
    vector<ll> gaps;
    gaps.reserve(N - 1);
    for (int i = 1; i < N; i++) {
        gaps.push_back(X[i] - X[i - 1]);
    }

    // Sort gaps descending
    sort(gaps.begin(), gaps.end(), greater<ll>());

    // We want to skip the largest M-1 gaps, summing the rest
    ll answer = 0;
    for (int i = M - 1; i < (int)gaps.size(); i++) {
        answer += gaps[i];
    }

    cout << answer << "\n";
    return 0;
}

How it works:

1. Read $N$ (number of houses) and $M$ (number of base stations).
2. If $M \ge N$, answer is 0 (one station per house).
3. Sort the house coordinates.
4. Compute the differences (gaps) between adjacent sorted coordinates.
5. Sort these gaps in descending order.
6. The optimal placement “breaks” at the largest $M-1$ gaps, so we sum all the remaining gaps to get the minimal total signal strength.
7. Output that sum.