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

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

。

代码

CPP

#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;
}

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

文章操作

P14566 题解

思路

代码

相关推荐

评论

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