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

· · 题解

题意简述

从长度为 N 的数组 A 中挑选 M 个元素排列，最小化

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

输出 L 即可。

题目分析

主要难点在证明上，做法实在是太简单了。

首先考虑 N = M 的情况，从而只需考虑怎么排列无需考虑选什么。

引理：在长度为 k 的正数序列中插入一个新的元素 x，L 不减。

证明：插在两端恰好使 L 增加了 |x^2 - y^2| \ge 0，无论两端的元素 y 是什么。接下来考虑插在了两数 a, b 之间的情形，此时这一小段变成了 a, x, b，记插入之后 L 变为 L'。则

\Delta L = L' - L = \big|x^2 - a^2\big| + \big|b^2 - x^2\big| - \big|b^2 - a^2\big|.

由三角不等式 |s + t| \le |s| + |t|，有 |s| + |t| - |s+t| \ge 0。令 s = x^2 - a^2，t = b^2 - x^2，则 s + t = b^2 - a^2，便可得出 \Delta L \ge 0，从而 L 不减。

结论：要么单调不增要么单调不减的排列 B 可以使 L 最小。

证明：记 \min B 为 B 中的最小值，\max B 为 B 中的最大值。那么根据引理，无论 \max B 和 \min B 在什么位置，都必有

L \ge (\max B)^2 - (\min B)^2

另一方面，将 B 升序排列后：

\min B = B_1 \le B_2 \le \dots \le B_M = \max B \\ \begin{aligned} L &= \sum_{i = 1}^{M - 1}\big|B_{i+1}^2 - B_i^2 \big| \\ &= \sum_{i = 1}^{M - 1}\big(B_{i+1}^2 - B_i^2\big) \\ &= B_M^2 - B_1^2 \\ &= (\max B)^2 - (\min B)^2 \end{aligned}

降序排列同理，从而我们得出 L 可以 \le (\max B)^2 - (\min B)^2。两个限制合并起来，便知 (\max B)^2 - (\min B)^2 是最小的 L。

接下来考虑 M \le N 的情况。根据前文，我们已经知道了 \min L 只取决于 \max B 和 \min B；所以使 L 尽可能小，要么让 \max B 尽可能小，要么让 \min B 尽可能大。

将 A 升序排列后，枚举左端点 l，令右端点为 r = l + M - 1，选取 A_{[l, r]} 这一段元素作为 B。此时有 \min B = A_l，\max B = A_{r}；显然有 A_r \le A_{r+1} \le \dots 从而 \max B 已经够小了，由于必须恰好选 M 张画所以 r 也不能再小了。只需对所有可能的 l 都计算一次 L，选出最小的那个即可。

参考代码

#include <algorithm>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::vector;

using u64 = unsigned long long;

int main() {

    size_t n, m;
    cin >> n >> m;

    vector<u64> a(n);
    for(u64 &x : a) cin >> x;
    std::sort(a.begin(), a.end());

    u64 minimum = 1'000'000'000'000ull;
    for(size_t L = 0; L + m <= n; ++L) {
        size_t R = L + m - 1;
        minimum = std::min(minimum, a[R] * a[R] - a[L] * a[L]);
    }

    cout << minimum;
    return 0;
}