P5682 [CSP-J2019 江西] 次大值
P5682 [CSP-J2019 江西] 次大值
题目描述
Alice 有 n n n 个正整数，数字从 1 ∼ n 1 \sim n 1∼n 编号，分别为 a 1 , a 2 , … , a n a_1,a_2, \dots , a_n a1,a2,…,an。
Bob 刚学习取模运算，于是便拿这 n n n 个数进行练习，他写下了所有
a i m o d a j ( 1 ≤ i , j ≤ n ∧ i ≠ j ) a_i \bmod a_j (1 \le i,j \le n \wedge i \neq j) aimodaj(1≤i,j≤n∧i=j)
的值，其中 m o d \bmod mod 表示取模运算。
Alice 想知道所有的结果中，严格次大值是多少。将取模后得到的所有值进行去重，即相同的结果数值只保留一个，剩余数中第二大的值就称为严格次大值。
输入格式
第一行一个正整数 n n n，表示数字个数。
第二行 n n n 个正整数表示 a i a_i ai。
输出格式
仅一行一个整数表示答案。
若取模结果去重后剩余数字不足两个，则输出 − 1 -1 −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 % 40\% 40% 的数据， 1 ≤ n , a i ≤ 100 1\le n,a_i \le 100 1≤n,ai≤100；
对于 70 % 70\% 70% 的数据， 1 ≤ n ≤ 3000 1\le n \le 3000 1≤n≤3000， 1 ≤ a i ≤ 1 0 5 1\le a_i \le 10^5 1≤ai≤105；
对于 100 % 100\% 100% 的数据， 3 ≤ n ≤ 2 × 1 0 5 3 \le n \le 2\times 10^5 3≤n≤2×105， 1 ≤ a i ≤ 1 0 9 1\le a_i \le 10^9 1≤ai≤109。
【样例 1 1 1 解释】
所有取模的结果为 { 4 , 4 , 4 , 1 , 0 , 5 , 1 , 0 , 5 , 2 , 1 , 1 } \{4,4,4,1,0,5,1,0,5,2,1,1\} {4,4,4,1,0,5,1,0,5,2,1,1}。
去重后有： { 0 , 1 , 2 , 4 , 5 } \{0,1,2,4,5 \} {0,1,2,4,5}，结果为 4 4 4。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;int a[300005];int main() {int n;cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];sort(a + 1, a + n + 1);n = unique(a + 1, a + n + 1) - a - 1;if (n <= 1) {cout << "-1\n";return 0;}cout << max(a[n - 2], a[n] % a[n - 1]) << '\n';return 0;
}