Starters 213-Mean Difference (easy) · znzryb

## 思路讲解

## AC代码

[https://www.codechef.com/viewsolution/1210385010](https://www.codechef.com/viewsolution/1210385010)



::: 源代码

```cpp
// by Gospel_rock
// title: Mean Difference (Easy)
// GROUP_NAME: START213B
// ONLINE_JUDGE_NAME: CodeChef

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1;
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);

ll lT;

void Solve(){
	ll N;
	cin>>N;
	vector<ll> A(N+5);
    FOR(i,1,N) {
        cin>>A[i];
    }
    if (N==1) {
        cout<<0<<"\n";
        return;
    }
    sort(A.begin()+1,A.begin()+N+1,greater<>());
    function f=[&](ll need_big) {
        if (need_big>=N) return 0ll;
        ll acc=0;
        FOR(i,1,need_big) {
            acc+=A[i];
        }
        acc+=A[N];
        acc/=(need_big+1);
        return abs(acc-A[N]);
    };
    ll l=0,r=N-1;
    while (r-l>2) {
        ll mid1=l+(r-l)/3;
        ll mid2=r-(r-l)/3;
        if (f(mid1)<=f(mid2)) {
            l=mid1;
        }else {
            r=mid2;
        }
    }
    ll ans=0;
    FOR(i,l,r) ans=max(ans,f(i));
    sort(A.begin()+1,A.begin()+N+1);
    l=0,r=N-1;
    while (r-l>2) {
        ll mid1=l+(r-l)/3;
        ll mid2=r-(r-l)/3;
        if (f(mid1)<=f(mid2)) {
            l=mid1;
        }else {
            r=mid2;
        }
    }
    FOR(i,l,r) ans=max(ans,f(i));
    cout<<ans<<"\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin>>lT;
    while(lT--)
        Solve();
    return 0;
}
/*
AC

*/
```


:::


## 心路历程（WA，TLE，MLE……）