CSP - J组：小核桃将积木堆成不超m堆的最小能量计算及代码详解

```cpp #include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; // 计算将一段区间内的积木移动到中位数位置所需的最小能量 int calculateCost(const vector<int>& positions, int left, int right) { vector<int> temp; for (int i = left; i <= right; ++i) { temp.push_back(positions[i]); } sort(temp.begin(), temp.end()); int median = temp[temp.size() / 2]; int cost = 0; for (int pos : temp) { cost += abs(pos - median); } return cost; } int main() { int n, m; cin >> n >> m; vector<int> positions(n); for (int i = 0; i < n; ++i) { cin >> positions[i]; } sort(positions.begin(), positions.end()); // dp[i][j] 表示将前 i 个积木堆成 j 堆所需的最小能量 vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX)); dp[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= min(i, m); ++j) { for (int k = j; k <= i; ++k) { if (dp[k - 1][j - 1] != INT_MAX) { int cost = calculateCost(positions, k - 1, i - 1); dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + cost); } } } } int ans = INT_MAX; for (int j = 1; j <= m; ++j) { ans = min(ans, dp[n][j]); } cout << ans << endl; return 0; } ``` 代码解释： 1. calculateCost函数： - 该函数用于计算将一段区间内的积木移动到中位数位置所需的最小能量。 - 首先将该区间内的坐标值提取到一个临时数组中并排序。 - 找到中位数，计算每个坐标值与中位数的差值的绝对值之和，即为所需能量。 2. 主函数： - 读取输入的积木数量`n`和最大堆数`m`，以及每个积木的坐标值。 - 对坐标值进行排序。 - 定义二维数组`dp`，`dp[i][j]`表示将前`i`个积木堆成`j`堆所需的最小能量。 - 初始化`dp[0][0] = 0`，表示没有积木且不堆时能量为0。 - 通过三重循环填充`dp`数组，对于每个`i`和`j`，枚举所有可能的分割点`k`，计算将前`k - 1`个积木堆成`j - 1`堆，再将第`k`到第`i`个积木堆成一堆的总能量，并取最小值。 - 最后遍历`dp[n][1]`到`dp[n][m]`，找到最小能量值并输出。 ######[AI问答 | 780点数解答 | 2026-02-07 18:38:58]