HJ182 画展布置
- 题目
- 题解(13)
- 讨论(9)
- 排行
中等 通过率：23.96% 时间限制：1秒 空间限制：256M
知识点双指针
校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
展厅共有 NN 幅画作，其艺术价值为整数 A1,A2,…,ANA1,A2,…,AN。策展人需选出其中 MM 幅依次摆放。设选出后排成一列的价值为 B1,…,BMB1,…,BM，定义一个画展的不和谐度 LL 满足：
L = ∑i=1M−1∣Bi+12−Bi2∣.L=∑i=1M−1∣∣Bi+12−Bi2∣∣.
请最小化 LL 并输出其最小可能值。
输入描述：
第一行输入两个整数 N,M(2≦M≦N≦105)N,M(2≦M≦N≦105)。
第二行输入 NN 个整数 A1…AN(1≦Ai≦105)A1…AN(1≦Ai≦105)。
输出描述：
输出一个整数，表示最小化后的 LL 值。
示例1
输入：
4 2 1 5 2 4
复制输出：
3
复制说明：
选择 {1,2}{1,2} 得到 L=22−12=3L=22−12=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; }