[C++知识库]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();
}