问题分析 我们需要找到一个排列 `p`，使得在将数组 `a` 的每个元素 `a_i` 加上排列 `p` 的对应元素 `p_i` 后，新数组中某个元素的出现次数最大化。我们的目标是找到这个最大出现次数。 关键观察 1. 排列的性质：排列 `p` 是 `1` 到 `n` 的一个排列，即 `p` 包含 `1` 到 `n` 的每个数字恰好一次。 2. 新数组的元素：新数组的元素为 `a_i + p_i`。我们需要选择一个 `p` 使得尽可能多的 `a_i + p_i` 相同。 3. 最大化相同元素的策略：为了使 `a_i + p_i` 相同，我们需要让 `a_i + p_i` 的值尽可能集中。这可以通过将 `a` 和 `p` 的排序方式结合起来实现。 解决思路 1. 排序：将数组 `a` 和排列 `p` 分别排序。排序 `a` 为升序，排序 `p` 为降序（或反之），这样可以最大化 `a_i + p_i` 的相同值的可能性。 - 具体来说，将 `a` 升序排列，`p` 降序排列（即 `p` 是 `n, n-1, ..., 1`），这样 `a_i + p_i` 的值会尽可能集中在某个范围内。 2. 统计频率：计算 `a_i + p_i` 的值，并统计每个值的出现频率。 3. 最大频率：找到频率的最大值，即为答案。 为什么这样排序？ - 如果我们不排序 `a` 和 `p`，`a_i + p_i` 的值会分散，难以形成相同的值。 - 将 `a` 升序和 `p` 降序排列后，`a_i + p_i` 的值会尽可能集中在中间值附近，从而增加相同值的概率。 算法步骤 1. 对于每个测试用例： - 读取 `n` 和数组 `a`。 - 将 `a` 排序为升序。 - 构造排列 `p` 为 `n, n-1, ..., 1`（即降序排列）。 - 计算 `a_i + p_i` 的所有值。 - 统计这些值的频率，找到最大频率。 - 输出最大频率。 示例验证 以第一个测试用例为例： - 输入： ``` 2 1 2 ``` - 排序 `a` 为 `[1, 2]`。 - 排列 `p` 为 `[2, 1]`。 - `a_i + p_i` 为 `[1+2, 2+1] = [3, 3]`。 - 频率统计：`3` 出现 `2` 次。 - 输出 `2`，与示例一致。 代码实现 ```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()); unordered_map<int, int> freq; int max_freq = 0; for (int i = 0; i < n; ++i) { int val = a[i] + (n - i); // p_i = n, n-1, ..., 1 freq[val]++; if (freq[val] > max_freq) { max_freq = freq[val]; } } cout << max_freq << endl; } return 0; } ``` 代码解释 1. 输入处理：读取测试用例数量 `t`。 2. 循环处理每个测试用例： - 读取 `n` 和数组 `a`。 - 对 `a` 进行升序排序。 - 使用哈希表 `freq` 统计 `a_i + p_i` 的频率，其中 `p_i` 是 `n - i`（即 `p` 是 `n, n-1, ..., 1`）。 - 在统计过程中更新最大频率 `max_freq`。 3. 输出结果：对于每个测试用例，输出 `max_freq`。 额外注意的逻辑点 1. 排列的构造：排列 `p` 是 `n, n-1, ..., 1`，这是为了与排序后的 `a` 配合最大化相同值的出现。 2. 排序的必要性：必须对 `a` 排序才能确保 `a_i + p_i` 的值集中，否则无法保证最大频率。 3. 哈希表的使用：使用哈希表统计频率是因为值的范围可能很大，直接数组统计不现实。 [2025-03-25 21:11:51 | AI写代码神器 | 1118点数解答]