题解：P14566 【MX-S12-T1】取模

· · 题解

思路

对于任意正整数 p，余数的取值范围是 [0, p-1]，当余数同时包含 0 和 p-1 时，得分为 p-1。

  1. 选择足够大的 p（如 p > \max(a)），此时余数就是原数，得分为 \max(a) - \min(a)；
  2. 选择 p = \max(a)，此时最大余数是次大值，最小余数是 0，得分为次大值。

步骤

  1. 对数组排序并去重（要是严格次大值）；
  2. 如果去重后只剩一个元素，得分为 0；否则，答案为极差和次大值中的最大值。

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100010];
signed main(){
    int T;
    cin>>T;
    int mod;
    int ans=0;
    int n;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+n+1);
        n=unique(a+1,a+n+1)-(a+1);
        ans=max(a[n]-a[1],a[n-1]);
        cout<<ans<<"\n";
    }
    return 0;
}