P5682 [CSP-J2019 江西] 次大值

Dijkstra_zyl · 2025-09-28 21:41:25 · 题解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int a[maxn];
set<int> s;
inline int read(){//手写快读 
    char ch = getchar();
    int s = 0,w = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') w *= -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
int main(){
    int n = read(),top = 0;
    while(n--) s.insert(read());
    if(s.size() < 2) return cout << "-1",0;
    for(int elem : s) a[++top] = elem;//导出去重后的数据
    cout << max(a[top-2],a[top] % a[top-1]);//取两者最大值即为答案 
    return 0;
}
/*Why:max(a[top-2],a[top]%a[top-1])?
    因为 a%b<b 
    但是 当a<b时,a%b=a,b%a<a
    在a数组中,a1 - a[top-3]是不可能为最大值的 
    所以只有两个答案:a[top]%a[top-1],a[top-2]
        为什么有  a[top]%a[top-1]? 因为a[top]%a[top-1]有可能>a[top-2] 
        为什么没有a[top-1]?        因为a[top]%a[top-1]<a[top-1] 且 a[top-2]<a[top-1] 
*/