c++描述 小小李老师喜欢玩一种数字游戏 —— 给数组添加一个排列，然后找出出现次数最多的元素。 最近，他找到了一个数组 a，并决定找出在给数组 a 添加某个排列后，他可以获得的数组中相同数字的最大数量。 更正式地说，小小李老师必须选择 n 的 任意一个 全排列 p1、p2、p3 …… pn，然后根据规则给 a 数组的每一项加上全排列对应的数字，即 ai = ai + pi，这样做会改变数组 a 的元素。之后，找出 a 数组中出现次数最多的元素，它的出现次数就是得分。 你需要帮助小小李老师，让他获得最高的得分。 长度为 n 的全排列是由 1 到 n 的 n 个不同整数以任意顺序组成的数组。 例如当 n = 5 时，[2,3,1,5,4] 是一个全排列，但 [1,2,2] 不是一个全排列，[1,3,4] 也不是一个全排列。 输入描述 每个测试包含多个测试用例 第一行包含一个整数 t（1 ≤ t ≤ 100） —— 测试用例的数量 每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 10006）—— 数组 a 的长度 每个测试用例的第二行包含 n 个整数 ai（1 ≤ ai ≤

问题重述 我们需要找到一个排列 `p`，使得将数组 `a` 的每个元素 `a_i` 加上排列 `p` 的对应元素 `p_i` 后，新数组中某个元素出现的次数最大化。我们需要计算这个最大出现次数。 关键观察 1. 排列的性质：排列 `p` 是 `1` 到 `n` 的一个排列，即 `p` 包含 `1` 到 `n` 的每个数字恰好一次。 2. 变换后的数组：对于每个 `a_i`，变换后的值为 `a_i + p_i`。我们需要选择一个排列 `p`，使得尽可能多的 `a_i + p_i` 相同。 3. 最大化相同值的数量：我们需要找到一个值 `x`，使得尽可能多的 `a_i` 满足 `a_i + p_i = x`。由于 `p` 是排列，`p_i` 的值是唯一的。 解决思路 1. 排序数组：将数组 `a` 排序。这样可以更容易地匹配 `a_i` 和 `p_i`。 2. 贪心匹配：为了使 `a_i + p_i` 尽可能相同，我们可以尝试让较大的 `a_i` 匹配较小的 `p_i`，反之亦然。具体来说： - 将 `a` 按升序排序，`p` 按降序排序（即 `p` 是 `n, n-1, ..., 1`），这样 `a_i + p_i` 的值会尽可能接近。 - 或者将 `a` 按升序排序，`p` 按升序排序（即 `p` 是 `1, 2, ..., n`），这样 `a_i + p_i` 的值会尽可能分散。 - 我们需要选择一种匹配方式，使得 `a_i + p_i` 的值的频率最大化。 3. 统计频率：对于排序后的 `a` 和 `p`，计算 `a_i + p_i` 的值，并统计每个值的出现次数。最大的出现次数就是答案。 具体步骤 1. 对每个测试用例： - 读取 `n` 和数组 `a`。 - 将 `a` 排序。 - 构造排列 `p` 为 `1` 到 `n` 的升序排列。 - 计算 `a_i + p_i` 的所有值，并统计这些值的频率。 - 最大的频率就是答案。 为什么这样有效 - 将 `a` 排序后，我们希望 `a_i + p_i` 的值尽可能集中。如果 `a` 是升序，`p` 是降序，那么 `a_i + p_i` 的值会集中在中间。 - 通过统计 `a_i + p_i` 的频率，可以找到最多有多少个 `a_i + p_i` 是相同的。 代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> #include <unordered_map> using namespace std; 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]; } sort(a.begin(), a.end()); vector<int> p(n); for (int i = 0; i < n; ++i) { p[i] = i + 1; } unordered_map<int, int> freq; int max_freq = 0; for (int i = 0; i < n; ++i) { int val = a[i] + p[i]; freq[val]++; if (freq[val] > max_freq) { max_freq = freq[val]; } } cout << max_freq << endl; } return 0; } ``` 代码解释 1. 输入处理：读取测试用例数量 `t`。 2. 循环处理每个测试用例： - 读取数组长度 `n` 和数组 `a`。 - 对数组 `a` 进行排序。 - 构造排列 `p` 为 `1` 到 `n` 的升序排列。 - 计算 `a_i + p_i` 的值，并用哈希表统计每个值的出现次数。 - 输出最大的出现次数。 3. 输出结果：对于每个测试用例，输出最大频率。 示例分析 以第一个测试用例为例： - 输入： ``` 2 1 2 ``` - 排序后的 `a`：`[1, 2]`。 - 排列 `p`：`[1, 2]`。 - `a_i + p_i`：`[1+1, 2+2] = [2, 4]`。 - 频率：`2` 出现 1 次，`4` 出现 1 次，最大频率为 1。但实际输出是 2，说明之前的思路有误。 重新思考 之前的思路可能有问题。我们需要重新考虑如何选择排列 `p` 以最大化相同 `a_i + p_i` 的数量。 正确思路 - 将 `a` 排序后，我们希望 `a_i + p_i` 的值尽可能相同。 - 一种有效的方法是让 `a_i` 和 `p_i` 的匹配使得 `a_i + p_i` 的值尽可能集中在某个值。 - 具体来说，将 `a` 升序排序，`p` 降序排序（即 `p` 是 `n, n-1, ..., 1`），这样 `a_i + p_i` 的值会集中在 `a[0] + p[0]` 和 `a[n-1] + p[n-1]` 之间。 - 统计 `a_i + p_i` 的频率，最大的频率就是答案。 修正后的代码 ```cpp #include <iostream> #include <vector> #include <algorithm> #include <unordered_map> using namespace std; 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]; } sort(a.begin(), a.end()); vector<int> p(n); for (int i = 0; i < n; ++i) { p[i] = n - i; } unordered_map<int, int> freq; int max_freq = 0; for (int i = 0; i < n; ++i) { int val = a[i] + p[i]; freq[val]++; if (freq[val] > max_freq) { max_freq = freq[val]; } } cout << max_freq << endl; } return 0; } ``` 重新分析示例 第一个测试用例： - 输入： ``` 2 1 2 ``` - 排序后的 `a`：`[1, 2]`。 - 排列 `p`：`[2, 1]`（因为 `n=2`，降序排列）。 - `a_i + p_i`：`[1+2, 2+1] = [3, 3]`。 - 频率：`3` 出现 2 次，最大频率为 2，与示例输出一致。 最终解答 通过将 `a` 升序排序，`p` 降序排序，可以最大化 `a_i + p_i` 的相同值的数量。统计这些值的频率，最大的频率就是答案。 三条额外需要注意的逻辑点 1. 排列 `p` 必须是 `1` 到 `n` 的排列，不能重复或遗漏任何数字。 2. 排序 `a` 和 `p` 的顺序（一个升序，一个降序）是关键，以确保 `a_i + p_i` 的值尽可能集中。 3. 统计频率时需要使用高效的哈希表，以处理较大的 `n`。 [2025-03-27 17:50:16 | AI写代码神器 | 1815点数解答]