题目链接

画展布置

题目描述

展厅共有 幅画作，其艺术价值为 。策展人需选出其中 幅依次摆放。设选出后排成一列的价值为 ，定义一个画展的不和谐度 满足：

请最小化 并输出其最小可能值。

解题思路

首先，我们需要分析不和谐度的计算公式 。为了让这个和最小，对于任意选定的一组 幅画，我们都应该将它们按照艺术价值从小到大进行排列。

假设我们选出的 幅画作，其价值排序后为 （即 ）。此时，由于 ，所以 ，公式中的绝对值可以被移除：

这个求和式是一个典型的伸缩和（Telescoping Sum）。展开后，中间项会相互抵消：

因此，问题被极大地简化了：我们需要从 幅画作中选出 幅，使得这 幅画中最大价值与最小价值的平方差最小。

要实现这个目标，最优的策略是：

  1. 首先，对所有 幅画作的艺术价值数组 进行升序排序。
  2. 排序后，为了让所选的 幅画作的最大值和最小值之差最小，我们必须选择数组 中一个连续的长度为 的子数组。
  3. 因此，我们只需要遍历（或“滑动”一个大小为 的窗口）所有可能的连续子数组，计算其最后一个元素与第一个元素的平方差，并找出这个差值的全局最小值。

这个算法的核心是排序和一次线性扫描，效率很高。

代码

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

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    long long min_l = LLONG_MAX;

    for (int i = 0; i <= n - m; ++i) {
        long long current_l = a[i + m - 1] * a[i + m - 1] - a[i] * a[i];
        min_l = min(min_l, current_l);
    }

    cout << min_l << endl;

    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        Arrays.sort(a);

        long minL = Long.MAX_VALUE;

        for (int i = 0; i <= n - m; i++) {
            long currentL = a[i + m - 1] * a[i + m - 1] - a[i] * a[i];
            minL = Math.min(minL, currentL);
        }

        System.out.println(minL);
    }
}

import sys

n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

a.sort()

min_l = float('inf')

for i in range(n - m + 1):
    current_l = a[i + m - 1]**2 - a[i]**2
    min_l = min(min_l, current_l)

print(min_l)

算法及复杂度

  • 算法：排序 + 滑动窗口。
  • 时间复杂度：，瓶颈在于对数组的排序。后续的滑动窗口扫描部分的时间复杂度为 。
  • 空间复杂度： 或 ，取决于排序算法使用的额外空间。总空间复杂度为 因为需要存储数组。