# [CSP-J2019 江西] 次大值 ## 题目描述 Alice 有 $n$ 个正整数，数字从 $1 \sim n$ 编号，分别为 $a_1,a_2, \dots , a_n$。 Bob 刚学习取模运算，于是便拿这 $n$ 个数进行练习，他写下了所有 $$a_i \bmod a_j (1 \le i,j \le n \wedge i \neq j)$$ 的值，其中 $\bmod$ 表示取模运算。 Alice 想知道所有的结果中，严格次大值是多少。将取模后得到的所有值进行去重，即相同的结果数值只保留一个，剩余数中第二大的值就称为严格次大值。 ## 输入格式 第一行一个正整数 $n$，表示数字个数。 第二行 $n$ 个正整数表示 $a_i$。 ## 输出格式 仅一行一个整数表示答案。 若取模结果去重后剩余数字不足两个，则输出 $-1$。 ## 样例 #1 ### 样例输入 #1 ``` 4 4 5 5 6 ``` ### 样例输出 #1 ``` 4 ``` ## 样例 #2 ### 样例输入 #2 ``` 4 1 1 1 1 ``` ### 样例输出 #2 ``` -1 ``` ## 样例 #3 ### 样例输入 #3 ``` 7 12 3 8 5 7 20 15 ``` ### 样例输出 #3 ``` 12 ``` ## 提示 【数据范围】 对于 $40\%$ 的数据，$1\le n,a_i \le 100$； 对于 $70\%$ 的数据，$1\le n \le 3000$，$1\le a_i \le 10^5$； 对于 $100\%$ 的数据，$3 \le n \le 2\times 10^5$，$1\le a_i \le 10^9$。 【样例 $1$ 解释】 所有取模的结果为 $\{4,4,4,1,0,5,1,0,5,2,1,1\}$。 去重后有：$\{0,1,2,4,5 \}$，结果为 $4$。

题目描述中给出了 Alice 有 n 个正整数，Bob 对这些数进行了取模运算，并求出了所有的模值。

我们需要找到去重后的严格次大值。

思路：
1. 将所有取模的结果进行去重；
2. 如果去重后的结果个数小于2，则输出-1；
3. 否则，输出去重后的第二大值。

以下是一个可能的 C++ 实现：

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

int main() {
    int n;
    std::cin >> n;

    std::vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
    }

    std::set<int> mod_nums;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                mod_nums.insert(nums[i] % nums[j]);
            }
        }
    }

    if (mod_nums.size() < 2) {
        std::cout << -1 << std::endl;
    } else {
        std::vector<int> unique_mod_nums(mod_nums.begin(), mod_nums.end());
        std::sort(unique_mod_nums.rbegin(), unique_mod_nums.rend());
        std::cout << unique_mod_nums[1] << std::endl;
    }

    return 0;
}

该实现利用 `set` 容器进行去重，并将去重后的结果放入 `unique_mod_nums` 向量中。然后，对 `unique_mod_nums` 进行排序，输出第二大的值。

注意：本实现在处理较大的数据集时可能效率较低。