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

要将数组 `a` 转换为数组 `b`，我们需要理解操作对数组 `a` 的影响，并计算出最小操作数。具体操作包括： 1. 增加或减少数组 `a` 的任意元素 1。 2. 复制数组 `a` 的任意元素并将其附加到数组 `a` 的末尾。 关键思路： - 我们可以通过增加或减少操作，将数组 `a` 中的元素任意调整，但每次操作只能改变一个元素的值，且变化量为 1。 - 复制操作则允许我们增加数组 `a` 的长度，但考虑到我们最终要将数组 `a` 转换成数组 `b`，这个操作主要用于匹配数组 `b` 中多出来的那个元素或者用于生成缺失但能通过调整得到的元素。 最优策略是： - 我们尝试将数组 `a` 中的每个元素调整到数组 `b` 中对应位置（或最接近的，如果长度不匹配）的元素值，并计算调整的总次数。 - 如果数组 `b` 的长度比 `a` 多一个元素，我们需要检查这个多余元素是否可以通过数组 `a` 中的某个元素通过增加/减少操作得到，或者通过复制已有的元素得到。 下面是 C++ 实现代码： ```cpp #include <iostream> #include <vector> #include <cmath> #include <map> #include <algorithm> using namespace std; int minOperationsToTransform(int n, const vector<int>& a, const vector<int>& b) { int operations = 0; map<int, int> freq_a; // Count the frequency of each element in array a for (int num : a) { freq_a[num]++; } // Calculate operations to transform each element in a to corresponding element in b for (int i = 0; i < n; ++i) { int diff = abs(a[i] - b[i]); operations += diff; // Update the frequency map freq_a[a[i]]--; if (freq_a[a[i]] == 0) { freq_a.erase(a[i]); } freq_a[b[i]]++; } // Handle the extra element in array b bool extra_element_matched = false; for (auto it = freq_a.begin(); it != freq_a.end(); ++it) { if (abs(it->first - b[n]) <= it->second) { operations += abs(it->first - b[n]); extra_element_matched = true; break; } } // If no existing element can be transformed to the extra element in b, // we need to create it via copy (which doesn't cost extra operations beyond the copy itself being counted as a match). if (!extra_element_matched) { // Find the closest element in freq_a to minimize operations int min_operations = INT_MAX; for (auto it = freq_a.begin(); it != freq_a.end(); ++it) { min_operations = min(min_operations, abs(it->first - b[n])); } operations += min_operations; } return operations; } int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector<int> b(n + 1); for (int i = 0; i < n + 1; ++i) { cin >> b[i]; } cout << minOperationsToTransform(n, a, b) << endl; } return 0; } ``` 逻辑点需要注意： 1. 频率统计：使用 `map` 统计数组 `a` 中各元素的出现频率，便于后续操作计算。 2. 差异计算：计算每个元素从 `a` 到 `b` 的差异，并累计操作次数。 3. 额外元素处理：特别处理数组 `b` 中多出的一个元素，找到最优的匹配或生成方式。 ######[AI写代码神器 | 1002点数解答 | 2025-03-10 21:04:57]