1622C - Set or Decrease - CodeForces Solution

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define ff              first
#define ss              second
#define ll             long long int
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int>>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             998244353
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
//mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rep(i,a,b)          for(ll i = a; i < b; ++i)
// #define f(i,s,e) for(long long int i=s;i<e;i++)
#define cf(i,s,e) for(long long int i=s;i<=e;i++)
#define rf(i,e,s) for(long long int i=e-1;i>=s;i--)
ll lstbt(ll val) { ll msk = val & (val - 1); return log2(val ^ msk);}
void c_p_c()
{
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif
}
ll countDigit(ll n) {
  return floor(log10(n) + 1);
}
ll power(ll base, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n % 2) {
			ans = (ans * base);
			n = n - 1;
		}
		else {
			base = (base * base);
			n = n / 2;

		}

	}
	return ans;
}
bool comp(pair<pair<ll,ll>,ll>p1,pair<pair<ll,ll>,ll>p2)
{
	if(p1.first.first==p2.first.first){
		return p1.first.second>p2.first.second;
	}
	else{
		return p1.first.first<p2.first.first;
	}
}
ll findsum(ll n){
	ll s=0;
	while(n>0){
		s+=n%10;
		n/=10;
	}
	return s;
}
	vector<ll>primes;

ll func(ll n ){
    ll cnt = 0 ;
    
    while(n % 2 == 0){
        n = n/2 ;
        primes.push_back(2);
        cnt++;
    }
    
    for(int i=3 ; i<= sqrt(n) ; ++i){
        
        while(n % i == 0){
            n = n/i ;
            primes.push_back(i);
            cnt++;
        }
        
    }
    
    if(n > 1) {
        primes.push_back(n);
        cnt++;
    }
    
    return cnt ;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	c_p_c();
	w(t){
		ll n,k;
		cin>>n>>k;
		ll arr[n+1];
		rep(i,0,n){
			cin>>arr[i];
		}
		sort(arr,arr+n);
		ll sum=0;
		ll pre[n+1]={0};
		for(ll i=n-1;i>=0;i--){
			sum+=arr[i];
			if(i!=n-1){
				pre[i]=pre[i+1]+arr[i];
			}
			else{
				pre[i]=arr[i];
			}
		}
		ll cnt=0;
		ll dif=sum-k;
		if(n==1){
			if(dif<=0){
				cout<<"0"<<endl;
			}else{
				cout<<dif<<endl;
			}
		}
		else if(dif<=0){
			cout<<"0"<<endl;
		}
		else{
			ll mini=dif;
			// rep(i,0,n){
			// 	cout<<arr[i]<<" ";
			// }
			// cout<<endl;
	for(int i=n-1;i>0;i--)
    {
        ll temp = n-i;
        // cout<<"temp "<<temp<<endl;
        // cout<<"dif "<<dif<<endl;
        // cout<<"pre[i] "<<pre[i]<<endl;
        // cout<<"upper "<<(dif - pre[i] + arr[0]*(temp))<<endl;
        ll temp2 = ceil((dif - pre[i] + arr[0]*(temp))*1.00/(temp+1));
        // cout<<"temp2 "<<temp2<<endl;
        if(temp2>0)
        mini = min(temp+temp2,mini);
        else
        mini = min(temp,mini);
    }
    cout<<mini<<endl;
		}


	}


}