最小极差分组2026 华为OD机试真题 6月28日华为OD上机新系统考试真题 100 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解题目描述给定 n 个整数你需要将它们任意分成两组且两组都不能为空。对于一组数它的极差定义为该组中的最大值减去最小值。设两组分别为第 1 组和第 2 组则它们的极差分别为第 1 组极差 第 1 组最大值 − 第 1 组最小值第 2 组极差 第 2 组最大值 − 第 2 组最小值你的目标是最小化这两个极差之和即最小化(max1−min1)(max2−min2)2026 华为OD机试真题 6月28日华为OD上机新系统考试真题 100 分题型输入描述第一行整数 n数字个数第二行n 个整数用逗号分隔输出描述最小极差之和整数示例1输入510,1,5,3,8输出6说明划分为 [10,8] 和 [1,5,3] 两组左极差 5-1 4右极差 10-8 2总和 6示例2输入51,1,9,1,9输出0说明分组为 [1,1,1] 和 [9,9]两组的极差均为 0和也为 0示例3输入21,2输出0说明只能分为两组每组一个数。每组的最大最小值是同一个数极差为 0。解题思路核心思想贪心 排序最优分割点一定在排序后数组的某个位置。关键观察 1. 排序后假设在位置 k 分割[0..k] 为左组[k1..n-1] 为右组 2. 左组最小值 nums[0]左组最大值 nums[k] 3. 右组最小值 nums[k1]右组最大值 nums[n-1] 4. 总极差 (nums[k] - nums[0]) (nums[n-1] - nums[k1])贪心策略 - 遍历所有可能的分割点 k0 到 n-2 - 找到使总极差最小的分割点算法步骤对数组排序初始化最小值为一个大数遍历 k 从 0 到 n-2 - 计算当前分割点的总极差 - 更新最小值返回最小极差复杂度分析时间复杂度O(n log n)排序占主导空间复杂度O(1)