思路

贪心 + 前缀和优化 + 滑动窗口优化

过程

代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
LL n, a[N], k, sum[N];

LL cal(LL l, LL r)
{
    int mid = l + r >> 1;
    LL cost = (mid - l - r + mid) * a[mid] - (sum[mid - 1] - sum[l - 1]) + sum[r] - sum[mid];
    return cost;
}

int main()
{
    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 ++) sum[i] = sum[i - 1] + a[i];
    LL l = 1, r = 1, ans = 1;
    while(r < n + 1)
    {
        while(cal(l, r) > k) l ++;
        ans = max(ans, r - l + 1);
        r ++;
    }
    cout << ans << endl;
    return 0;
}