题解 P5682 【[CSPJX2019]次大值】

installb · 2019-11-26 20:07:01 · 题解

这题还是有很多要考虑的点的，稍微说一说解题过程。

首先本题要求的是严格次大值，所以有两个相同的数没有意义（简单分析一下可以发现，不需要考虑 a_i=a_j 的情况）。于是我们先把序列从小到大排序并去重。假设原序列排序、去重后剩下的序列为 a_1,a_2,\ldots,a_n。

最大值一定是 a_{n-1}\bmod a_n=a_{n-1}。以下分两种情况讨论 a_i\bmod a_j 的结果，简单证明：

然后我们可以发现，a_{n-2}\bmod a_n=a_{n-2} 是所有一个数对比它大的数取模得到的结果中的次大值。我们还要找出一个数对比它小的数取模得到的结果中的次大值，和刚才的值比较。

看起来需要枚举，其实不必。假设这个选择是 a_i\bmod a_j，那么如果 j\leq n-2，由于 a\bmod b < b，这个值一定小于 a_{n-2}。

于是 j\geq n-1 只剩下一种取法：i=n,j=n-1，即 a_n\bmod a_{n-1}。

这两个比较，取较大的，必定就是次大值。

代码也很简短：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;

int n;
int a[300005];

int main(){
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    sort(a + 1,a + 1 + n); n = unique(a + 1,a + 1 + n) - a - 1;
    // 排序+去重
   a[0] = 0;
    if(n <= 1) printf("-1\n");
   // 无解特判
    else printf("%d\n",max(a[n - 2],a[n] % a[n - 1]));
    return 0;
}