回溯

看到这题的第一反应是回溯，规定dfs(i, j)表示考虑前i个数字，还剩下j次修改；对于每一个数字，都有2种选择：

  • 选择它：j-1
    1. 可以+1也可以-1
    2. 选了第i个数，下一次还能接着选（可以剪枝：例如上一次是加1，那么再选它也应该是加1，否则没有意义）
  • 不选择它：j不变

这是最朴素的回溯，而且没有剪枝，肯定是超时了（后来我用对数器和下面的代码验证了一下（n=30，k=5，100组），基本可以认为它是正确的。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int n, k, a[N];

int res = 0;

void dfs(int i, int j)
{
    if (i < 0 || j == 0)
    {
        unordered_map<int, int> map;
        for (int i = 0; i < n; i++) map[a[i]]++;
        for (auto &e : map) res = max(res, e.second);
        return;
    }
    // 选，-1
    a[i]--;
    dfs(i - 1, j - 1);dfs(i, j - 1);
    a[i]++;
    // 选，+1
    a[i]++;
    dfs(i - 1, j - 1);dfs(i, j - 1);
    a[i]--;
    // 不选
    dfs(i - 1, j);
}

signed main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    dfs(n - 1, k);
    cout << res;
}

前缀和+滑动窗口

这道题要求的是经过k次加减操作后的序列中最大的相同元素个数，那么排序过后，这些元素就会挨在一起。那么问题转化为对一个排序后的数组，求一个区间在k次加减操作后，使得区间内的元素都相同，且区间长度最长。

算法核心：对于一组排序后的数，并想通过最少的增减操作将它们全部变成同一个数时，选择中位数作为目标值可以最小化所需的总操作次数。这是因为中位数最靠近所有元素的中间位置，调整这些数字到中位数的代价最小。

函数 f(l, r) 计算将区间 [l, r] 内所有元素变为 a[mid] 所需的操作次数。核心思想是：将左边的元素都增加到 a[mid]，将右边的元素减少到 a[mid]，然后计算总的操作次数。

公式的推导过程如下：

  • s[r] - s[mid]：[mid+1, r] 区间内所有元素的和。
  • s[mid-1] - s[l-1]：[l, mid-1] 区间内所有元素的和。
  • a[mid] * (r - mid)：[mid+1, r] 区间内所有元素都变为 a[mid] 所需的操作次数。
  • a[mid] * (mid - l)：[l, mid-1] 区间内所有元素都变为 a[mid] 所需的操作次数。

前缀和：计算数组 a 的前缀和数组 s，s[i] 表示前 i 个元素的总和。

滑动窗口的思路还是比较直观的：找到一个窗口，使得它尽量通过小于或等于k次的操作得到，这里用了一点小贪心，因为如果对一个数字进行多次操作，那么操作肯定都是一样的（只加或者只减，加减混用相当于都浪费了），所以用的总操作数越多，最终得到的区间也就越长。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int a[N], s[N];

int f(int l, int r)
{
    int mid = (l + r) >> 1;
    int sub_sum = s[r] - s[mid] - (s[mid - 1] - s[l - 1]);
    int op_sum = a[mid] * (r - mid) - a[mid] * (mid - l);
    return sub_sum - op_sum;
}

signed main()
{
    int n, k;
    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++) s[i] = s[i - 1] + a[i];
    int left = 1, right = 1, res = 0;
    while (right <= n)
    {
        while (f(left, right) > k) left++;
        res = max(res, right - left + 1);
        right++;
    }
    cout << res << endl;
}

二分优化

二分查找：

  • 外层循环遍历数组中的每个元素，以它为区间的左边界 i。
  • 使用二分查找来确定右边界 mid，以便在 k 次操作内尽可能扩展区间 [i, mid]。
  • 每次通过 f(i, mid) 计算操作次数，如果次数不超过 k，则更新答案 res 为当前区间长度 mid - i + 1。
  • 二分查找结束后，输出 res，即为最大化某个元素频率后的最大出现次数。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int a[N], s[N];

int f(int l, int r)
{
    int mid = (l + r) >> 1;
    int sub_sum = s[r] - s[mid] - (s[mid - 1] - s[l - 1]);
    int op_sum = a[mid] * (r - mid) - a[mid] * (mid - l);
    return sub_sum - op_sum;
}
signed main()
{
    int n, k;
    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++) s[i] = s[i - 1] + a[i];
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int l = i, r = n; // 遍历每一个区间
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (f(i, mid) <= k)
            {
                l = mid + 1;
                res = max(res, mid - i + 1);
            }
            else r = mid - 1;
        }
    }
    cout << res << endl;
}