自动搬运

查看原文

来自洛谷，原作者为

	Souture **

搬运于2025-08-24 23:13:00，当前版本为作者最后更新于2025-04-13 10:21:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

第一次水题解有点紧张

本题我们很容易想到先排序，利用前缀和暴力的思想对每个数字之间的贡献求出并累加，只需要滑动一次窗口即可求出最小的 L ， 但是说不出来这样为什么对。

这里我们来简单证明一下这样贪心的正确性。

---

题意

定义选取并排列后的画作艺术价值序列为

$$B_1, B_2, \dots, B_M,$$

对应的平方为

$$B_1^2, B_2^2, \dots, B_M^2.$$

让我们求

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

三角不等式

对任意实数 a 和 b，有三角不等式

$$|a+b| \le |a|+|b|.$$

当且仅当 a 与 b 同号（或至少其中一个为 0）时取等号。

及其推广：

$$\begin{aligned} \left|\sum_{k=1}^na_k\right|\leq\sum_{k=1}^n|a_k|. \end{aligned} $$

当且仅当 $$ a_k$$ 的符号都相同（允许个别为零，即所有非零项同正或同负）.

根据三角不等式，对于任意实数序列都有：

$$\left|B_2^2 - B_1^2\right| + \left|B_3^2 - B_2^2\right| + \cdots + \left|B_M^2 - B_{M-1}^2\right| \ge \left|B_M^2 - B_1^2\right|. $$

因此，必有：

$$L \ge \left|B_M^2 - B_1^2\right|.$$

何时取等号

当且仅当序列

$$B_1^2, B_2^2, \dots, B_M^2,$$

是单调的（即递增或递减）时，三角不等式取等号。又注意到，由于所有艺术价值 $B_i$ 均为正，故 $B_i^2$ 与 $B_i$ 的单调性一致。

因此，当我们将选中的画作按艺术价值从小到大或从大到小排列时，有

$$L = B_M^2 - B_1^2.$$

优化思路

对于固定的一组 $M$ 幅画作，最优排列顺序为使它们按照艺术价值的单调顺序排列，从而使得

$$L = B_M^2 - B_1^2.$$

为了使得 $L$ 最小，我们需要从所有可能的选取中选择那一组画作，使得所选画作中最大的艺术价值和最小的艺术价值差异（经过平方）最小。设原始数组为

$$A_1, A_2, \dots, A_N,$$

经过排序后记为

$$A_{1} \le A_{2} \le \dots \le A_{N}.$$

则可以证明最优方案总可以在排序后的数组中选择连续的 $M$ 个数，这样选出的最小值为 $A_{i}$，最大值为 $A_{i+M-1}$，对应的 $L$ 为

$$L = A_{i+M-1}^2 - A_{i}^2.$$

结论

综上，题目中

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

经排序后，最优排列下转化为了

$$L = B_M^2 - B_1^2,$$

而最小化 $L$ 就等价于在排序后的数组中找到一个长度为 $M$ 的连续子区间，使得

$$A_{i+M-1}^2 - A_{i}^2,$$

最小。

至此，我们将原评价指标转化为了

$$\min L = \min_{i}\left(A_{i+M-1}^2 - A_{i}^2\right). $$

---

代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

#define endl '\n'
#define all(v) v.begin(), v.end()

void sol()
{
    int n, m; cin >> n >> m;
    vector<int> A(n);
    vector<i64> B(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        B[i] = 1LL * A[i] * A[i];
    }

    sort(all(B));

    i64 ans = LLONG_MAX;
    for (int i = m - 1; i < n; i++) {
        ans = min(ans, B[i] - B[i - m + 1]);
    }

    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sol();
    return 0;
}