题解：CF2013D Minimize the Difference

Meickol · 2024-11-19 10:38:22 · 题解

提供一个二分的解法。

由题意条件可知，因为我们让 a_i-1,a_{i+1}+1，并且我们希望使得序列中极差最小。

虽然原序列并未保证单调，但是我们可将原序列通过若干次题目给定的操作使其构造成单调不降的序列，因为题目操作相当于从前面拿一部分给后面，并且保证构造后的序列每个值尽可能接近。

保证了序列单调性后，即可考虑二分答案，我们要使得数列中极差最小只需要使得序列中的最大值最小且序列中的最小值最大。

通过两次二分答案求出这两个值后做差即可得到答案。

关于二分答案函数的细节，当确定一个二分值 x 时，我们枚举整个序列，如果序列当前位置的值大于 x，我们可以考虑将当前这个位置的数不断 -1 使其变成 x，然后因为我们对这个位置 -1 操作，相应的减的次数可以留给后面需要的数让它们进行 +1 操作。

对于求最小值的最大时时，我们只需要判一下我们前面减一的操作提供给后面加一的机会（即余量）是否够弥补后面加一的需要即可。

对于求最大值的最小时，我们即需要判断前面减一操作提供给后面加一的机会（即余量）是否消耗完即可，若没消耗完，则说明可以继续加，说明最小值会比 x 更大。

#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int N=2e5+5;
int n;
LL a[N];
bool check(LL x){
    LL res=0;
    rep(i,1,n){
        if(a[i]>x) res+=a[i]-x;
        if(a[i]<x){
            if(res<x-a[i]) return false; //余量不够，即无法让最小值无法增大到x，说明x偏大
            res-=x-a[i];
        }
    }
    return true;
}
bool check2(LL x){
    LL res=0;
    rep(i,1,n){
        if(a[i]>x) res+=a[i]-x;
        if(a[i]<x){
            res-=x-a[i];
            res=max(res,0LL);
        }
    }
    if(res>0) return false; //有余量，即无法让序列最大值减小到x，说明x偏小
    else return true;
}
void solve(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    LL l=1,r=1e12;
    while(l<r){
        LL mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    LL minx=l;
    l=1,r=1e12;
    while(l<r){
        LL mid=l+r>>1;
        if(check2(mid)) r=mid;
        else l=mid+1;
    }
    LL maxx=l;
    cout<<maxx-minx;
}