解题思路

将能量值从小到大排序。固定选取数量 $k$ 和选中元素的最大下标 $r$，最优目标值为 $a_r$。若选中了 $r-k+1$ 之前的元素，则区间 $[r-k+1,r]$ 内必有未选中的元素。用后者替换前者，操作次数不会增加。因此，仅需考虑连续区间。

设区间 $[l,r]$ 的元素和为 $s$，将其全部增加到 $a_r$ 的代价为：

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

固定 $l$，右移 $r$ 时，原有元素的目标值不会降低，新元素无需操作，故代价不减。于是依次枚举 $r$，若代价超过 $m$，便右移 $l$，直到区间可行。被舍弃的左端点以后仍不可行，故此时的 $[l,r]$ 是以 $r$ 为右端点的最长可行区间。取所有区间长度的最大值即可。

两个指针均至多移动 $n$ 次，总时间复杂度为 $O(n\log n)$。代价不超过 $(n-1)\times2\times10^{12}<10^{18}$，使用 long long。

参考代码

415 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,ans=0;
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		while(a[i]*(i-l+1)-sum>m)
		{
			sum-=a[l];
			l++;
		}
		ans=max(ans,i-l+1);
	}
	cout<<ans<<'\n';
	return 0;
}