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

题目描述

给定N幅画作的艺术价值 $A=(A_1, A_2, \ldots, A_N)$，从中选出M幅进行排列，要求最小化相邻画作艺术价值平方差的绝对值和： $$ L = \sum_{i=1}^{M-1} |B_{i+1}^2 - B_i^2| $$。

算法思路

关键发现

1. 数学性质：对于排序后的数组，连续子序列的L值等于首尾元素平方差，即$$ L = B_M^2 - B_1^2 $$。
2. 排序必要性：排序后相邻元素差值最小化。
3. 滑动窗口：只需检查所有长度为 $M$ 的连续子序列。

优化策略

1. 预处理排序。
2. 直接计算窗口首尾平方差。
3. 处理边界情况($M = 1$)。

完整代码

#include <iostream>
#include <vector>
#include <algorithm>  // 用于sort函数
#include <climits>    // 用于LLONG_MAX

using namespace std;

int main() {
    // 输入输出加速（对大数据量很关键）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    /* 输入处理 */
    int N, M;
    cin >> N >> M;  // 读取画作数量N和需要选择的画作数M
    
    vector<int> A(N);  // 存储艺术价值的数组
    for (int i = 0; i < N; ++i) {
        cin >> A[i];  // 读取每幅画作的艺术价值
    }
    
    /* 关键步骤1：艺术价值排序 */
    // 升序排序后相邻元素差值最小化
    sort(A.begin(), A.end());
    
    /* 边界情况处理：当只需要选1幅画时 */
    if (M == 1) {
        cout << 0 << '\n';  // 没有相邻画作，差值为0
        return 0;
    }
    
    /* 初始化最小L值为最大可能值 */
    long long min_L = LLONG_MAX;  // 使用long long防止大数溢出
    
    /* 滑动窗口遍历所有长度为M的连续子序列 */
    for (int i = 0; i <= N - M; ++i) {
        // 计算当前窗口首尾元素的平方差
        // 注意转换为long long防止int溢出
        long long diff = (long long)A[i+M-1]*A[i+M-1] - (long long)A[i]*A[i];
        
        // 更新最小值（比if判断更简洁的写法）
        min_L = min(min_L, diff);
    }
    
    /* 输出结果 */
    cout << min_L << '\n';  // 使用'\n'比endl更快
    
    return 0;
}