题解 | 加减

加减

https://ac.nowcoder.com/acm/contest/11214/I

回溯

看到这题的第一反应是回溯,规定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 的前缀和数组 ss[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;
}
全部评论

相关推荐

Pandaileee:校友加油我现在也只有一个保底太难了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务