【CSP】CSP-J 2019 江西真题 | 次大值 luogu-P5682 （适合GESP四、五级及以上考生练习）
CSP-J 2019江西省真题- 次大值，主要考察排序算法与取模运算的数学性质，重点在于对不同数据的分情况讨论与逻辑推导分析，适合GESP四、五级及以上考生练习，难度⭐⭐⭐，洛谷难度等级普及/提高-。
P5682 [CSP-J 2019 江西] 次大值
题目要求
题目描述
Alice 有 $n$ 个正整数，数字从 $1 \sim n$ 编号，分别为 $a_1,a_2, \dots , a_n$。
\[a_i \bmod a_j (1 \le i,j \le n \wedge i \neq j)\]
Bob 刚学习取模运算，于是便拿这 $n$ 个数进行练习，他写下了所有的值，其中 $\bmod$ 表示取模运算。
Alice 想知道所有的结果中，严格次大值是多少。将取模后得到的所有值进行去重，即相同的结果数值只保留一个，剩余数中第二大的值就称为严格次大值。
输入格式
第一行一个正整数 $n$，表示数字个数。
第二行 $n$ 个正整数表示 $a_i$。
输出格式
仅一行一个整数表示答案。
若取模结果去重后剩余数字不足两个，则输出 $-1$。
输入输出样例 #1
输入 #1
1
2
4
4 5 5 6
输出 #1
1
4
输入输出样例 #2
输入 #2
1
2
4
1 1 1 1
输出 #2
1
-1
输入输出样例 #3
输入 #3
1
2
7
12 3 8 5 7 20 15
输出 #3
1
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$。
题目分析
本题是一道非常经典的数学思维与算法题，乍看似乎需要两两取模求解（复杂度为 $O(N^2)$），但 $N$ 最大为 $2 \times 10^5$，如果用暴力枚举法必然会超时（Time Limit Exceeded）。因此我们需要挖掘取模计算背后的数学规律。
数学规律分析：
当我们求两个数互相取模 $a_i \bmod a_j$ 时，有以下几种情况：
- 若 $a_i < a_j$，则 $a_i \bmod a_j = a_i$。（这就是说小数字对大数字取模，结果等于小数字本身）
- 若 $a_i \ge a_j$，则 $a_i \bmod a_j < a_j \le a_i$。（结果一定严格小于除数 $a_j$）
因为要找“去重后”的次大值，我们可以将原数组首先进行排序并在逻辑上去重。假设去重后不同元素的序列按升序排列为 $U = [u_1, u_2, \dots, u_k]$。
最大值是怎么产生的？ 根据第 1 点，要想结果最大，就让最大数字去充当除数，也就是利用 $u_{k-1} \bmod u_k = u_{k-1}$。 也就是说，整个集合所有取模组合中最大的那个值，必然是原序列中严格第二大的数字（即 $u_{k-1}$）。
严格次大值怎么产生？ 既然绝对最大值是 $u_{k-1}$，那么有资格成为次大值的，只有可能是下面两个候选者：
- 原始序列中严格第三大的数字，也就是利用 $u_{k-2} \bmod u_k = u_{k-2}$ 产生。
- 最大的数字对第二大数字取余的结果：$u_k \bmod u_{k-1}$。这一项有时候也会意外地比较大。
因此，严格次大值必然是 $\max(u_{k-2},\, u_k \bmod u_{k-1})$。
综合以上分析，我们需要根据唯一数字的不同个数进行分类讨论：
- 当 $k = 1$ 时：也就是所有数字是一样的，任意两个取模必定为 $0$。此时去重后结果不足 $2$ 种，按题意要求输出
-1。 - 当 $k = 2$ 时：最大的取模结果是 $u_{0}$ (由 $u_{0} \bmod u_{1}$ 得来)；而严格次大的结果一定是由大数除小数得来，即 $u_{1} \bmod u_{0}$。
- 当 $k \ge 3$ 时：根据我们前文的分析，次大值为 $\max(u_{k-3},\, u_{k-1} \bmod u_{k-2})$（如果将数组切换为以 $0$ 起始下标的表示）。
示例代码
解法一：降序遍历寻找最大的三个不同数字
按照上述推论，我们可以先对全体数字进行排序，然后从大到小依次找到最大的三个不同的互异数字再进行分类讨论结算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <algorithm>
#include <iostream>
// 全局数组，防止申请大空间时引发内存溢出问题（栈溢出）
int ary[200005];
int main() {
int n;
std::cin >> n;
// 读入输入数据
for (int i = 0; i < n; i++) {
std::cin >> ary[i];
}
// 对数组进行升序排序，时间复杂度 O(N log N)
std::sort(ary, ary + n);
int count_diff = 1; // 记录找到了多少个【不同的数字】
int big_one = ary[n - 1]; // 预设数组最后一个元素（排序后全局最大的数字）
int big_two = 0, big_thr = 0; // 用来存第二大（次大）和第三大的数字
// 因为排序过了，我们从后往前遍历寻找严格的次大和第三大数字即可
for (int i = n - 2; i >= 0; i--) {
// 如果已经成功找到了三个最大且彼此不同的数字，就可以提前退出循环以节约时间
if (count_diff == 3) {
break;
}
// 当我们只录入了一个最大数，且当前遇到的数字不同于它时，它就是第二大数字
if (count_diff == 1 && ary[i] != big_one) {
count_diff++;
big_two = ary[i];
}
// 当我们已经录入了两个数值，且当前遇到的数字不同于它们时，它就是第三大数字
if (count_diff == 2 && ary[i] != big_two) {
count_diff++;
big_thr = ary[i];
}
}
// 根据收集到的不同的数字个数（范围 1 到 3），开始分情况结算
if (count_diff == 1) {
// 数据里只有一种相同的数字，取模总是 0，符合条件的唯一数字不足两个
std::cout << -1;
} else if (count_diff == 2) {
// 数据去重后只有两种数字，最大的取模情况是由小的数得到，即 big_two
// 而严格次大的取模结果只能是大数%小数去产生，即：最大数字取模次大数字
std::cout << big_one % big_two;
} else {
// 原数组含有超过三种以上的去重数字时：
// 比较【第三大数字】与【最大数字对第二大数字取余】，选取它们中间的较大者
std::cout << std::max(big_thr, big_one % big_two);
}
return 0;
}
解法二：巧用 C++ 标准模板库（STL）中 std::unique 简化逻辑
为了更优雅地获得上述数组中“去重”的一系列不重复数字，我们可以直接利用 <algorithm> 头文件中强大的 std::unique 去重算法来帮我们轻松提取这段升序的不重复数字内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>
// 全局数组存放数据
int a[200005];
int main() {
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
// 第 1 步：与上一版本相同，首先进行升序排序
std::sort(a, a + n);
// 第 2 步：std::unique 会通过前后对比将不重复的元素紧凑排在数组前面
// 并返回最后新生成无重复逻辑序列段尾部的下一位指针。
// 将该结果指针减去原数组首地址(a)，正好能够直接得到【不同元素的个数 k】！
int k = std::unique(a, a + n) - a;
// 第 3 步：直接利用提取出的长度为 k 的唯一且升序序列，复用推导思想完成分类判断
if (k == 1) {
// 只有 1 个不同的元素，任何互相取余的结果一定都是 0，由于不足两项故返回 -1
std::cout << -1 << std::endl;
} else if (k == 2) {
// 只有 2 个不同的元素（索引互通为 0 和 1）
// 最大的数字一定可以被 a[0] % a[1] 产生。
// 所以次大必须是大数字除小数，即：
std::cout << a[1] % a[0] << std::endl;
} else {
// 至少有 3 个不同的元素，末端最大的三个互异数值对应位置肯定是下标的 [k-1], [k-2] 以及 [k-3]
// 按照之前的推导方法，这二者中的极大值代表了所有排列组合能产生的严格次大元素：
// 候选一：严格第三大数字，即 a[k-3]
// 候选二：最大数字 % 严格次大数字，即 a[k-1] % a[k-2]
std::cout << std::max(a[k - 3], a[k - 1] % a[k - 2]) << std::endl;
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
