【错题集-编程题】加减（枚举 + 前缀和 + 滑动窗口 + 贪心）

牛客对应题目链接：加减 (nowcoder.com)

一、分析题目

1. 贪心：尽可能选择一些挨得比较近的数，让他们变成相同的数（排序）。前缀和可以从 O(N) 变到 O(1)。
2. 枚举所有的区间，找出区间内所有数变成相同的数的最小代价 cost <= k 的最大区间。滑动窗口可以从 O(N^2) 变到 O(N)。
3. 如何求一个区间的最小 变到代价 cost。（转化成数学问题：数轴上有一些点，选取一个位置，使得所有点到它的距离之和最小）

结论：选择最中间的点。

二、代码

// 值得学习的代码
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL n, k;
LL arr[N];
LL sum[N]; // 前缀和数组

LL cal(int l, int r)
{
    int mid = (l + r) / 2;
    return (mid - l - r + mid) * arr[mid] - (sum[mid - 1] - sum[l - 1]) + (sum[r] - sum[mid]);
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    sort(arr + 1, arr + 1 + n);
    // 初始化前缀和数组
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i];
 
    int left = 1, right = 1, ret = 1;
    while(right <= n)
    {
        // 进窗⼝
        LL cost = cal(left, right);
        while(cost > k) // 判断
        {
            left++; // 出窗⼝
            cost = cal(left, right);
        }
        // 更新结果
        ret = max(ret, right - left + 1);
        right++;
    }

    cout << ret << endl;
 
    return 0;
}

三、反思与改进

这道题目结合了好几个不同的知识点，后面需要重复练习，很锻炼代码能力，需要多做这种混合知识点的类型题。