1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
|
#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 CD=complex<double>; static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1; static constexpr ll mod=(ll)1e9+7; 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; }
|