分析

tag:思维、排序

简单来说如果两个积木之间的距离最小，我们可以将它们放到同一个堆中，这样可以使得这两个积木之间的距离对总能量消耗的贡献最小。因此，我们可以先对积木排序，然后取相邻的距离，按从小到大对距离进行排序，然后选取前 $n-m + 1$ 个距离最小的物品（也就是消耗前$n-m$个距离）放到一个堆里，其余的物品放到单独的一个堆中。这样，我们可以以最小的能量消耗得到$m$堆积木。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    scanf("%d %d", & n, & m);

    vector < int > positions(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", & positions[i]);
    }

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

    vector < long long > distances(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        distances[i] = positions[i + 1] - positions[i];
    }

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

    long long result = 0;
    for (int i = 0; i < n - m; ++i) {
        result += distances[i];
    }

    printf("%lld\n", result);
    return 0;
}