Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
5.3 kB
1
Indexable
Never
/**
* @Author:51D
**/

#include <iostream>
#include <string>
#include <utility>
#include <cstdlib>
#include <limits>
#include <cmath>
#include <climits>
#include <vector>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <algorithm>
#include <sstream>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long long ll;

#define mod 1000000007
#define inf 1e9
#define f(i,n) for(int i=0;i<n;i++)
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define w(t) ll tt;cin>>tt;while(tt--)
#define pb push_back
#define endl "\n"
#define read(arr,n) for(ll i=0;i<n;i++){cin>>arr[i];};
#define pi pair<ll,ll>
#define all(arr) arr.begin(),arr.end()

// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//options: less,greater_equal,less_equal,greater

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

const int N=3e5+5;
const long long infll = 0x3f3f3f3f3f3f3f3fLL;
int p[N];

ll modulo(ll a, ll b, ll n){
    ll x=1, y=a; 
    while (b > 0) {
        if (b%2 == 1) {
            x = (x*y) % n; // multiplying with base
            
        }
        y = (y*y) % n; // squaring the base
        b /= 2;
    }
    return x % n;
}

ll modmod(ll a,ll b,ll c){
    // Fermats Little Theorem
    // A^(M-1) = 1 (mod M) if M is a prime.
    // So write B^C as x*(M-1) + y
    
    ll y = modulo(b,c,mod-1);
 
    return modulo(a,y,mod);
}

ll value[1000001];
void fillNumberOfDivisorsArray(){
    for(ll i=1;i<=1000000;i++){
        for(ll j=1;i*j<=1000000;j++){
            value[i*j]++;
        }
    }
}

vector<ll> prime;
bool is_composite[N];

void sieve(ll n) {

    fill(is_composite,is_composite + n,false);

    for (ll i=2;i<n;i++){

        if(!is_composite[i]){
            prime.push_back(i);
        }

        for (int j=2;i*j < n;j++){
            is_composite[i * j] = true;
        }
    }
}

void addEdge(vector<ll> adj[],ll u,ll v){
    adj[u].pb(v);
    adj[v].pb(u);
}

ll __lcm(ll a,ll b){
    return a*b/(__gcd(a,b));
}

vector<ll> fact;
void factorialFill(){
    fact.pb(1);
    fact.pb(1);
    for(ll i=2;i<=1000000;i++){
        fact.pb((i%mod * fact.back()%mod)%mod);
    }
}
ll getfact(ll num){
    return fact[num]%mod;
}

ll getBits(ll num){
    return log2(num) + 1;
}


struct cmp {
    bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
        return a.first < b.first;
    }
};

/*
Your observations here:



*/

ll getAnswer(ll mid,vector<ll>& arr,ll sum,ll k){
    vector<ll> temp = arr;

    ll n = temp.size();

    ll cnt = abs(temp[0] - mid);

    sum -= temp[0];
    sum += mid;

    temp[0] = mid;

    if(sum<=k){
        return cnt;
    }

    for(ll i=n-1;i>0;i--){
        sum -= temp[i];
        sum += temp[0];

        if(temp[i]!=temp[0]){
            cnt++;
        }

        temp[i] = temp[0];

        if(sum<=k){
            return cnt;
        }
    }

    return cnt + (sum-k);
}

void solve(ll tc){
    ll n,k;
    cin>>n>>k;

    vector<ll> arr(n);

    ll sum = 0;

    for(ll i=0;i<n;i++){
        cin>>arr[i];
        sum += arr[i];
    }

    if(sum<=k){
        cout<<0<<endl;
        return;
    }

    // Binary on lowest number set

    sort(arr.begin(),arr.end());

    ll l = -1e17;
    ll r = arr[0];

    ll ans = LLONG_MAX;

    while(l<r){
        ll mid = (l+r+1)/2;

        ll a1 = getAnswer(mid,arr,sum,k);
        ll a2 = getAnswer(mid-1,arr,sum,k);

        if(a2>=a1){
            ans = min(ans,a1);
            l = mid;
        }
        else{
            r = mid-1;
        }
    }

    cout<<ans<<endl;
}

int main() {

    FIO;
    #ifndef ONLINE_JUDGE
        freopen("debug.txt", "w", stderr);
    #endif
    ll tt;
    cin>>tt;
    for(ll i=1;i<=tt;i++){
        solve(i);
    }

    return 0;
}