题解 P5682 【[CSPJX2019]次大值】

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

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

首先它要求严格次大值 所以有两个相同的数没有意义...先排序+去重
假设原序列去重后剩下的序列为a_1,a_2,...,a_n

由于 a\ mod\ b < a 所以最大值一定是a_{n-1}\ mod\ a_n
简单证明:

• 1.对于a_1到a_{n-2} 使其取模比它们大的数 就是本身 一定比a_{n-1}小
• 2.如果一个数模比它小的数 被模的数不可能是a_n 那么最后值一定小于a_{n-1}

然后我们可以想到 很明显a_{n-2}\ mod\ a_n是所有一个数模比它大的数中次大值x
我们还要找出一个数模比它小的数中次大值 和刚才的值x比较
看起来得枚举了 其实不必
假设这个选择是a_j\ mod\ a_i 那么如果i\leq n-2 这个值一定小于x
于是i\geq n-1 只剩下一种取法:j=n,i=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;
}