排序+二分+贪心

题意：给定n个数，最多操作k词，每次操作将其中一个数+1，求最终出现次数最多的数的出现次数。

首先要明确，最终出现次数最多的数是一定是数组中的数。

假设最终解是a[i]，那么len这段长度都会变成a[i]，因为每次操作只能将数+1，所以只能将一些小的数变成a[i]。若a[i]不是数组中的数，那么意味着，我们需要花费更大的代价将一些数变成a[i]，而我们完全可以找一个比a[i]小的最大的数来代替a[i]。

其次，出现次数一定是[1, n]，区间最大长度是n，因为数组最大n个数。设操作k次，最优解的区间是len，随着k的增大，那么最优解区间len也随之增大(单调性)，这样我们可以通过二分来做，二分len。

如何判断给定len的区间，是否能够通过不超过k次操作存在将[l, r]区间都变成a[r]？(滑动窗口+前缀和)

我们枚举所有可能的区间，对于每个区间，我们要将[l, r]区间的和变成最终区间和是sum = a[r] * len是否能够不超过k。这一步是$O(N)$的。

1. 排序
2. 二分最优解len，二分出最大的len
3. 对于每个len，用滑动窗口+前缀和判断能否不超过k次，将[l, r]区间的数变成a[r]

时间复杂度$O(NlogN)$，空间复杂度$O(N)$

AC代码

class Solution {
public:
    typedef long long LL;
    vector<LL> s;
    int n;

    int maxFrequency(vector<int>& nums, int k) {
        n = nums.size();
        s = vector<LL>(n + 1);
        sort(nums.begin(), nums.end());//排序
        for (int i = 0 ; i < n ; i ++) s[i + 1] = s[i] + nums[i]; //预处理前缀和
        //二分
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(nums, mid, k)) l = mid;
            else r = mid - 1;
        }
        return r;
    }

    bool check(vector<int>& nums, int len, int k) {
        for (int i = 0 ; i + len - 1 < n ; i ++) {
            int j = i + len - 1;
            LL sum = nums[j] * 1ll * len;
            LL cur = s[j + 1] - s[i];
            LL cnt = sum - cur; //要操作的次数
            if (cnt <= k) return true;
        }
        return false;
    }
};