【蓝桥杯】画展布置

画展布置

题目描述

画展策展人小蓝和助理小桥为即将举办的画展准备了 $N$ 幅画作，其艺术价值分别为 $A_1,A_2,\dots ,A_N$。他们需要从这 $N$ 幅画中挑选 $M$ 幅，并按照一定顺序布置在展厅的 $M$ 个位置上。如果随意挑选和排列，艺术价值的变化可能会过于突兀，导致观众的观展体验不够流畅。

为了优化布置，他们查阅了《画展布置指南》。指南指出，理想的画展应使观众在欣赏画作时，艺术价值的过渡尽量平缓。指南建议，选择并排列 $M$ 幅画，应使艺术价值的变化程度通过一个数值 $L$ 来衡量，且该值越小越好。数值 $L$ 的定义为：

$$L=\sum _{i=1}^{M-1}|B_{i+1}^2-B_i^2|$$

其中 $B_i$ 表示展厅第 $i$ 个位置上画作的艺术价值。

现在，他们希望通过精心挑选和排列这 $M$ 幅画作，使 $L$ 达到最小值，以提升画展的整体协调性。请你帮他们计算出这个最小值是多少。

输入格式

输入共两行。

第一行包含两个正整数 $N$ 和 $M$，分别表示画作的总数和需要挑选的画作数量。

第二行包含 $N$ 个正整数 $A_1,A_2,\dots ,A_N$，表示每幅画作的艺术价值。

输出格式

输出一个整数，表示 $L$ 的最小值。

输入输出样例 #1

输入 #1

4 2
1 5 2 4

输出 #1

3

说明/提示

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$2\le M\le N\le 10^3$，$1\le A_i\le 10^3$。
• 对于 $100\%$ 的评测用例，$2\le M\le N\le 10^5$，$1\le A_i\le 10^5$。

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

【思路分析】

将准备好的N幅画从小到大排序，根据公式每两两求平方差，选择最小的即可

但是这样写一定会超时

import java.io.*;
import java.util.*;
public class Main {static final int N = 100010;static int[] a = new int[N];static int[] show = new int[N];public static void main(String[] agrs) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] row1 = br.readLine().split(" ");int n = Integer.parseInt(row1[0]);int m = Integer.parseInt(row1[1]);String[] data = br.readLine().split(" ");for(int i = 0; i < n; i++) {a[i] = Integer.parseInt(data[i]);}Arrays.sort(a, 0, n);long res = 2147483647;//第一个画的选择for(int i = 0; i <= n - m + 1; i++) {long t = 0;boolean flag = false;//m个画展位置for(int j = i; j < i + m; j++) {if(j + 1 < i + m && j + 1 < n) {flag = true;if(flag) {t += Math.abs((long)a[j] * (long)a[j] - (long)a[j + 1] * (long)a[j + 1]);}} } if(flag) {//System.out.println(t);res = Math.min(res, t);}}System.out.println(res);br.close();}
}

我们观察到每次都是求固定窗口大小的和，我们可以前缀和预处理出来，这样优化后即可ac

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;public class Main {static final int N = 100010;static int[] a = new int[N];static long[] s = new long[N];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] row1 = br.readLine().split(" ");int n = Integer.parseInt(row1[0]);int m = Integer.parseInt(row1[1]);String[] data = br.readLine().split(" ");for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(data[i]);}// 对数组进行排序Arrays.sort(a, 0, n);// 预处理前缀和数组for (int i = 1; i < n; i++) {s[i] = s[i - 1] + Math.abs(a[i] * a[i] - a[i - 1] * a[i - 1]);}long res = Long.MAX_VALUE;// 枚举所有可能的 m 幅画的组合for (int i = m - 1; i < n; i++) {long cur = s[i] - s[i - m + 1];res = Math.min(res, cur);}System.out.println(res);br.close();}
}