[CSP-J 2019 江西] 次大值

知识点

取模运算、排序、分类讨论

解题思路

先排序去重。若只剩一种值，所有取模结果均为0，答案为-1。否则记最大、次大不同值为M、B，第三大不同值为C（不存在则取0）。取模结果的最大值是B，严格次大值为max(C,M%B)。

正确性说明

任意取模值都小于除数且不超过被除数。设最大、次大不同值为M、B，则B%M=B，所以最大结果为B。对于小于B的结果：被除数小于B时至多C；被除数为B且余数小于B时，其除数不超过C；被除数为M时，除数为B产生M%B，其余更小除数不超过C。若有C，C%M=C，故严格次大为max(C,M%B)。若只有两种不同值，M%B可由不同值的两个位置得到；又因n≥3，至少一种值重复，两个不同位置的同值相模可产生0。因此两值情况仍以max(0,M%B)成立。只有一种值时所有结果均为0，不存在严格次大。

易错点

需取严格次大并按数值去重；不能把最大值重复出现视为次大。两种不同值时至少一种值重复（n≥3），故0必能出现。

复杂度

时间O(n log n)，去重数组空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<long long>a(n);for(auto&v:a)cin>>v;sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());int m=a.size();if(m==1){cout<<-1<<'\n';return 0;}long long ans=a[m-1]%a[m-2];if(m>=3)ans=max(ans,a[m-3]);cout<<ans<<'\n';}