P11797 题解

getchar_unlocked · 2025-02-23 19:10:07 · 题解

题目传送门

思路

无论增加，都是整体增减，所以若集体增加 x，最终结果即为 f(x)=\max\limits_{i=1}^n\lvert a_i+x\rvert。

而 f(x) 其实是个单峰函数，可以进行二分。具体地，判断 f(x) 与 f(x+1) 的值，判断其状态上升或下降，并最终找到最小值即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=105;
int n,a[N];
int check(int x){
    int res=0;
    for(int i=1;i<=n;++i)
        res=max(res,llabs(a[i]+x));
    return res;
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    sort(a+1,a+n+1);
    int l=-1e18,r=1e18,ans=LLONG_MAX;
    while(l<=r){
        int mid=(l+r)>>1,ck=check(mid);
        ans=min(ans,ck);
        if(ck>check(mid+1))
            l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}