蓝桥杯备考：数学问题模运算---》次大值

这道题，由于数据规模是2e5，我们直接暴力的话是一定会超时的

所以我们得想个办法，我们先把所有的数排序去重

我们先想想如果要找最大值，怎么找

这时候我们要分类讨论

①如果是大数模小数，那结果肯定是小于小数的，我们让小数最大，但是又必须得让大数比小数大，所以小数只能选择a[n-1] 大数选择a[n]也就是a[n]%a[n-1]，这个式子模出来的值一定是小于a[n-1]的

②如果是小数模大数，结果就是小数，我们要让小数最大，也就是a[n-1]%a[n] 这个时候模出来的值就是a[n-1] 所以最大值就是a[n-1]%a[n]

but，我们要求的不是最大值而是次大值

我们继续分类讨论

①如果是大数模小数，结果肯定是小于小数的，因为最大值是a[n-1]%a[n]，我们的次大值一定是小于a[n-1]的，所以应该是a[n]%a[n-1]，结果小于a[n-1]

②如果是小数模大数，结果就是小数，这时候我们得让小数第二大，也就是a[n-2]%a[n]，结果就是a[n-2]

最后我们对这两种情况取max，就是我们的答案了！
 

#include <iostream>
#include <algorithm>
using namespace std;
int n;
const int N = 2e5+10;
int a[N];
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);cout << max(a[n-2]%a[n],a[n]%a[n-1]);return 0;
}