题解：P12134 [蓝桥杯 2025 省 B] 画展布置

· · 题解

第一次水题解有点紧张

本题我们很容易想到先排序，利用前缀和暴力的思想对每个数字之间的贡献求出并累加，只需要滑动一次窗口即可求出最小的 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;
}