C++ 实现：计算将长度为 n 的数组 a 转换为长度为 n+1 的数组 b 的最小操作数

要将数组 `a` 转换为数组 `b`，我们需要仔细分析题目所给的三种操作： 1. 增加数组 `a` 的任意元素 1。 2. 减少数组 `a` 的任意元素 1。 3. 复制数组 `a` 的任意元素并将其附加到数组 `a` 的末尾。 注意到第三种操作实际上可以看作是将数组 `a` 的某个元素值“复制”到新的位置，而不是真的要求通过物理复制来实现数组长度的增加。这个操作允许我们通过增加数组长度来匹配数组 `b` 的长度，并且可以用新的元素值来“凑”出数组 `b` 的各个元素。 关键观察是： - 我们可以通过增加或减少操作来将数组 `a` 的元素调整到任意整数值。 - 由于可以复制元素，因此最终我们总能通过复制和调整来“凑”出数组 `b`。 最小操作数实际上取决于两个数组元素值之间的“差异总和”的最小化。具体地，我们需要最小化所有 `|ai - bi|` 的总和，其中 `i` 遍历数组 `a` 和 `b` 的对应位置（前 `n` 个位置），并且额外处理数组 `b` 的最后一个元素，因为它在数组 `a` 中没有直接对应元素。 一种直观的解法是： 1. 计算数组 `a` 和数组 `b` 前 `n` 个元素之间的绝对差异总和。 2. 将数组 `b` 的最后一个元素通过增加/减少操作，尽量“映射”到数组 `a` 中某个元素的最小差异上。 由于 `a` 可以通过复制任意元素来“凑”出 `b` 的长度，因此 `b` 的最后一个元素实际上可以看作是要“插入”到 `a` 中，使得总操作数最小。 下面是 C++ 代码实现： ```cpp #include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); vector<int> b(n + 1); for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < n + 1; ++i) { cin >> b[i]; } // 计算前 n 个元素的差异总和 long long diff_sum = 0; for (int i = 0; i < n; ++i) { diff_sum += abs(a[i] - b[i]); } // 处理 b 的最后一个元素，找到插入到 a 中的最小差异 sort(a.begin(), a.end()); long long min_diff = LLONG_MAX; for (int num : a) { min_diff = min(min_diff, abs(num - b[n])); } // 输出结果 cout << diff_sum + min_diff << endl; } return 0; } ``` 代码逻辑点： 1. 差异计算：首先计算数组 `a` 和数组 `b` 前 `n` 个元素的绝对差异总和。 2. 排序和最小差异：对数组 `a` 排序，然后找到 `b` 的最后一个元素插入到 `a` 中的最小差异。 3. 输出总和：输出前 `n` 个元素的差异总和加上最小差异作为最终结果。 ######[AI写代码神器 | 819点数解答 | 2025-03-08 21:02:34]