画展布置-排序

解题思路

这个问题要求我们从N幅画中选择M幅，并排列它们，使得相邻画作艺术价值平方的差的绝对值之和最小。

首先，我们可以观察到，对于任意两幅画的艺术价值a和b，|a² - b²| = |a-b|·|a+b|。这意味着，如果我们想要最小化|a² - b²|，我们应该选择艺术价值接近的画作放在相邻位置。

一个直观的策略是：

1. 对所有画作的艺术价值进行排序

2. 选择M幅连续的画作（因为连续的画作艺术价值差异最小）

3. 按照特定顺序排列这M幅画作，使得L最小

对于排列顺序，我们可以证明，最优的排列方式是按照艺术价值从小到大或从大到小排列。

代码实现

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

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> values(N);
    for (int i = 0; i < N; i++) {
        cin >> values[i];
    }
    
    // 排序
    sort(values.begin(), values.end());
    
    // 计算所有可能的连续M幅画作的L值
    long long min_L = LLONG_MAX;
    
    for (int i = 0; i <= N - M; i++) {
        vector<int> selected(values.begin() + i, values.begin() + i + M);
        
        // 计算按照从小到大排列的L值
        long long L1 = 0;
        for (int j = 0; j < M - 1; j++) {
            long long diff = (long long)selected[j+1] * selected[j+1] - (long long)selected[j] * selected[j];
            L1 += abs(diff);
        }
        
        // 计算按照从大到小排列的L值
        long long L2 = 0;
        for (int j = 0; j < M - 1; j++) {
            long long diff = (long long)selected[M-j-2] * selected[M-j-2] - (long long)selected[M-j-1] * selected[M-j-1];
            L2 += abs(diff);
        }
        
        min_L = min(min_L, min(L1, L2));
    }
    
    cout << min_L << endl;
    return 0;
}

解释

对于样例输入： N=4, M=2, 艺术价值为[1, 5, 2, 4]

排序后为[1, 2, 4, 5] 可能的连续2幅画作为：[1,2], [2,4], [4,5]

计算L值：

[1,2]: |2² - 1²| = |4 - 1| = 3

[2,4]: |4² - 2²| = |16 - 4| = 12

[4,5]: |5² - 4²| = |25 - 16| = 9

最小的L值为3。