洛谷P12134题解

分析

题意

我们需要从 $N$ 幅画中挑选 $M$ 幅，按一定顺序排列，使得相邻画作艺术价值平方差的绝对值之和 $L$ 最小。其中 $L$ 的定义为：

$$L=\sum_{i=1}^{M-1} |B_{i+1}^2 - B_i^2|$$

目标是找到这个最小的 $L$ 值。

思路

观察 $L$ 的表达式，由于绝对值内是平方差，当我们将挑选的画作按平方值排序后，$B_{i+1}^2 \geq B_i^2$，此时 $|B_{i+1}^2 - B_i^2| = B_{i+1}^2 - B_i^2$，$L$ 可简化为相邻元素平方差的总和。

排序后的平方值数组中，连续元素的差值总和最小。也就是说，从排序后的平方值数组中，找长度为 $M$ 的连续子数组，使相邻元素差值之和最小。

先计算第一个长度为 $M$ 的窗口的差值和，再通过滑动窗口更新（减去离开窗口的差值，加上进入窗口的新差值），找到最小值。

代码

#include <bits/stdc++.h>
#define int long long//一定要开 long long，虽然这么写不是那么优雅
using namespace std;
int s[100005];//平方数组
signed main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        s[i] = a * a;//艺术价值的平方
    }
    sort(s, s + n);
    int ans = 0;
    for (int i = 0; i < m - 1; i++) {
        ans += s[i + 1] - s[i];
    }
    //滑动窗口
    int cur = ans;
    for (int i = 1; i <= n - m; i++) {
        cur = cur - (s[i] - s[i - 1]) + (s[i + m - 1] - s[i + m - 2]);
        ans = min(cur, ans);
    }
    cout << ans;
    return 0;
}