问题重述 我们需要找到一个排列 `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点数解答]