题目 3321: 蓝桥杯2025年第十六届省赛真题-画展布置
时间限制: 2s 内存限制: 192MB 提交: 673 解决: 130
题目描述
画展策展人小蓝和助理小桥为即将举办的画展准备了 N 幅画作，其艺术价 值分别为 A1, A2, . . . , AN。他们需要从这 N 幅画中挑选 M 幅，并按照一定顺序 布置在展厅的 M 个位置上。如果随意挑选和排列，艺术价值的变化可能会过于 突兀，导致观众的观展体验不够流畅。
为了优化布置，他们查阅了《画展布置指南》。指南指出，理想的画展应使 观众在欣赏画作时，艺术价值的过渡尽量平缓。指南建议，选择并排列 M 幅 画，应使艺术价值的变化程度通过一个数值 L 来衡量，且该值越小越好。数值 L 的定义为：
其中 Bi 表示展厅第 i 个位置上画作的艺术价值。
现在，他们希望通过精心挑选和排列这 M 幅画作，使 L 达到最小值，以提升画展的整体协调性。请你帮他们计算出这个最小值是多少。
输入格式
输入共两行。
第一行包含两个正整数 N 和 M，
分别表示画作的总数和需要挑选的画作数量。
第二行包含 N 个正整数 A1, A2, . . . , AN，表示每幅画作的艺术价值。
输出格式
输出一个整数，表示 L 的最小值。
样例输入复制
4 2
1 5 2 4
样例输出复制
3
提示
【评测用例规模与约定】
对于 40% 的评测用例，2 ≤ M ≤ N ≤ 103，1 ≤ Ai ≤ 103。
对于 100% 的评测用例，2 ≤ M ≤ N ≤ 105，1 ≤ Ai ≤ 105。
1.分析
排序后，类似双指针遍历。
2.代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAX = 1e5 + 10;
LL n,m,a[MAX],t,re;
int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a + n);int j = 0;for (int i = 1; i < m; i++) {t += (a[i - 1] + a[i]) * (a[i] - a[i - 1]);}re =t;for (int i = m,j=1; i < n; i++,j++) {t -= (a[j] - a[j-1]) * (a[j] + a[j-1]);t+= (a[i - 1] + a[i]) * (a[i] - a[i - 1]);re = min(re, t);}cout << re << endl;return 0;
}
