2019 江西真题 | 次大值 luogu-P5682

4
4 5 5 6

4

4
1 1 1 1

-1

7
12 3 8 5 7 20 15

12

#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;
}

#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;
}