解题思路

将 $a$ 升序排序，最优选择可取为连续区间 $[l,r]$，代价为：

$$\sum_{i=l}^r(a_r-a_i)=(r-l+1)a_r-\sum_{i=l}^r a_i$$

维护前缀最优长度 $k$。加入 $a_r$ 后，只可能改进为 $k+1$，因此只检查末尾 $k+1$ 项。可行则增长，否则左端右移 $1$，维持长度；窗口本身允许暂不合法。最终长度即答案。

总时间复杂度 $O(n\log n)$。

参考代码

368 Bcpp

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=500005;
ll a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	ll m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	int l=1;
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		if(a[i]*(i-l+1)-sum>m)sum-=a[l++];
	}
	cout<<n-l+1<<'\n';
	return 0;
}