C++(clang++ 11.0.1) 解法, 执行用时: 53ms, 内存消耗: 2188K, 提交时间: 2022-12-22 15:04:46

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,k;
ll a[100010];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)a[i]+=a[i-1];
    ll l=1,r=2;
    ll ans=1;
    while(l<=n&&r<=n)
    {
        ll m=(l+r)>>1;
        ll x=a[m]-a[m-1];
        if(x*(m-l+1)-a[m]+a[l-1]+a[r]-a[m]-x*(r-m)<=k)ans=max(ans,r-l+1),r++;
            else l++;
    }
    cout<<ans;
    return 0;
}

Python3 解法, 执行用时: 508ms, 内存消耗: 15832K, 提交时间: 2022-10-26 23:40:23

n,k=map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
arr1 = [0 for i in range(n+1)]
for i in range(1,n+1):
    arr1[i]=arr1[i-1]+arr[i-1]    
p1=0
p2=0
maxlen=1
while(p2<n):
    p=(p2+p1)//2
    step= arr[p]*(p-p1+1)-(arr1[p+1]-arr1[p1]) +arr1[p2+1]-arr1[p+1]-arr[p]*(p2-p)
    if(step<=k):
        maxlen=max(maxlen,p2+1-p1)
        p2=p2+1
    elif p1<p2:
        p1=p1+1
print(maxlen)