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

zxh_qwq · 2025-11-22 13:51:09 · 题解

P14566 题解

思路

以下令 x 为序列 a 中的严格次大值，y 为最大值，z 为最小值。

• 当 p > y 时，答案为 y-z。

• 当 x < p \le y 时，取 p=y 最优，答案为 x。（在 y-z \le x 的前提下满足上式。容易发现 y-z>x 的时候这种情况一定不优。）

• 当 p \le x 时，答案一定小于 p，即小于第二种情况。

所以答案为 \max(x,y-z)。

特别的，当序列中所有元素均相等（没有严格次大值）时，答案为 0。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[214514];
main(){
//  freopen("mod4.in","r",stdin);
//  freopen("mod4.out","w",stdout); 
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        sort(a+1,a+n+1);
        int l=n-1;
        a[0]=-1;
        while(a[l]==a[n])l--;
        if(l==0)cout<<0;
        else cout<<max(a[l],a[n]-a[1])<<"\n";
    }
    return 0;
}