华为 · 双指针 · 算法编程题
华为 双指针 N ≤ 1e5 时限 1 秒 / 256 MB

题目描述

展厅共有 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 值。

样例共 1 组

样例 1 · 选择 \1,2 得到 L=2^2-1^2=3 ,为最小值。
输入
4 2
1 5 2 4
输出
3

算法解析依据充分

考点:双指针

数据规模 N ≤ 1e5 | 限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:M ≤ 1e5,N ≤ 1e5
  • 元素值域:A_i ≤ 1e5(注意整数类型选择,避免溢出)
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:双指针

用两个指针协同移动,把两层循环的 O(n²) 优化到 O(n)。

思路框架(双指针 通法 · 非本题专属)

  1. 判断是「对撞指针」(一左一右向中间靠拢)还是「快慢指针」(同向不同速)。
  2. 确定指针移动的单调条件:什么情况下移动左指针,什么情况下移动右指针。
  3. 每一步根据当前指针位置更新答案,直到指针相遇或越界。
  4. 常配合有序性使用:无序时先排序。

实现要点:写成 while (l < r) 循环最清晰,切记每轮至少有一个指针移动,否则死循环。

复杂度:时间 O(n)(排序则 O(n log n)) | 空间 O(1)

该范式的通法易错点

  • 指针移动条件写反,漏解或死循环。
  • 两指针同时移动导致跳过合法解。

对照本题

  • 数据规模 N ≤ 1e5,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1:输入 4 2 / 1 5 2 4 → 输出 3

选择 \1,2 得到 L=2^2-1^2=3 ,为最小值。

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:华为机试编程模拟题1。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解