C. Set or Decrease

Set or Decrease"/>

C. Set or Decrease

题目链接

#include <iostream>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <map>
using namespace std;
#define int long long
const int N = 200010;
typedef pair<int,int>PII;
int a[N],s[N];
int n,k;
bool check(int len,int x)
{int sum=s[n-len]-a[1]+x*(len+1);return sum<=k;
}
void solve()
{memset(s,0,sizeof s);cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];int res=2e9;for(int i=0;i<=n-1;i++){int l=-1e9,r=1e9;while(l<r){int mid=l+r+1>>1;if(check(i,mid))l=mid;else r=mid-1;}res=min(res,max(0ll,a[1]-l)+i);}cout<<res<<'\n';
}signed main()
{int T;cin>>T;while(T--)solve();
}