P1019小核桃与积木堆 普及- CSP-J组 排序 贪心 标准IO 传统题 来源 TomAnderson 时间限制 1000ms 内存限制 256MB 通过/尝试次数 1787/2245 题目描述 数字线上的某些整数坐标处有 n n 个积木，小核桃不喜欢积木四处散落。所以他打算搬动积木，堆成不超过 m m 堆的积木堆。将坐标值 X X 的积木全部搬到到坐标值 Y Y 处，需要消耗 ∣ X − Y ∣ ∣X−Y∣ 的能量。 计算小核桃把玩具堆成不超过 m m 堆需要消耗的最小能量值。 输入描述 第一行包含两个整数，之间以一个空格隔开，分别是 n n, m m， n n 代表积木总数量， m m 代表最大堆数。 第二行包含 n n 个整数， x i x i ​ 表示积木 i i 所处坐标值为 a i a i ​ ，之间以一个空格隔开。 输出描述 计算出把积木堆成不超过 m m 堆需要消耗的最小能量值。 input1 复制 4 1 10 5 3 12 output1 复制 9 input2 复制 4 2 1 20 3 100 output2 复制

```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]`，找到最小能量值并输出。 [2026-02-07 18:38:58 | AI问答 | 780点数解答]