展厅共有 N 幅画作,其艺术价值为整数 A_1,A_2,... ,A_N 。策展人需选出其中 M 幅依次摆放。设选出后排成一列的价值为 B_1,... ,B_M ,定义一个画展的不和谐度 L 满足: L=Σ_i=1^M-1|B_i+1^2-B_i^2|. 请最小化 L 并输出其最小可能值。
第一行输入两个整数 N,M(2≤ M≤ N≤ 10^5) 。 第二行输入 N 个整数 A_1... A_N(1≤ A_i≤ 10^5) 。
输出一个整数,表示最小化后的 L 值。
4 2 1 5 2 4
3
考点:双指针
数据规模 N ≤ 1e5 | 限制 1 秒 / 256MB | 标准输入输出
推荐方向:双指针
用两个指针协同移动,把两层循环的 O(n²) 优化到 O(n)。
思路框架(双指针 通法 · 非本题专属)
实现要点:写成 while (l < r) 循环最清晰,切记每轮至少有一个指针移动,否则死循环。
复杂度:时间 O(n)(排序则 O(n log n)) | 空间 O(1)
该范式的通法易错点
对照本题
样例 1:输入 4 2 / 1 5 2 4 → 输出 3
选择 \1,2 得到 L=2^2-1^2=3 ,为最小值。
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:华为机试编程模拟题1。