华为OD机试 - 最小极差分组（Python/JS/C/C++/Go 新系统 100分）-开发者社区

华为OD机试新系统统一考试题库清单（持续收录中）以及考点说明（Python/JS/C/C++）。

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++/Go）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

给定 n 个整数，你需要将它们任意分成两组，且两组都不能为空。
对于一组数，它的极差定义为该组中的最大值减去最小值。
设两组分别为第 1 组和第 2 组，则它们的极差分别为：

• 第 1 组极差 = 第 1 组最大值 − 第 1 组最小值

• 第 2 组极差 = 第 2 组最大值 − 第 2 组最小值
你的目标是最小化这两个极差之和，即最小化：
(max1 − min1) + (max2 − min2)
请输出这个最小值。

二、测试用例

测试用例1：

1、输入

5
1 1 9 1 9

2、输出

3、说明

排序后：

1 1 1 9 9

最大相邻差为：

9 - 1 = 8

整体极差也是：

9 - 1 = 8

因此：

8 - 8 = 0

可以分成：

[1, 1, 1]
[9, 9]

两组极差都是 0。

测试用例2：

1、输入

5
10 1 5 3 8

2、输出

3、说明

排序后：

1 3 5 8 10

相邻差：

2 2 3 2

最大相邻差为 3。

整体极差：

10 - 1 = 9

所以：

9 - 3 = 6

可以划分为：

[1, 3, 5]
[8, 10]

极差分别为 4 和 2，总和为 6。

三、解题思路

先将 n 个整数从小到大排序，记为a[0], a[1], ..., a[n-1]。

两组中每组的贡献只与该组的最大值和最小值有关。考虑一组数对应区间[min1, max1]，另一组对应[min2, max2]。如果两个区间发生交叉或包含，那么两个极差之和不会小于整个数组的极差a[n-1] - a[0]；而把排序后的数组从某两个相邻元素之间切开，得到的结果一定不超过整体极差。因此最优方案一定可以选择为：排序后前 k 个元素属于第一组，剩余元素属于第二组。

假设在a[k]和a[k+1]之间切分，则：

第一组极差：
a[k] - a[0]

第二组极差：
a[n-1] - a[k+1]

两者之和为：

a[n-1] - a[0] - (a[k+1] - a[k])

其中a[n-1] - a[0]是固定值，因此要让结果最小，就要让切分位置的相邻差
a[k+1] - a[k]尽可能大。

所以最终答案为：

整体极差 - 最大相邻差

四、Python算法源码

importsysdefmain():data=sys.stdin.read().split()ifnotdata:returnn=int(data[0])nums=list(map(int,data[1:1+n]))# 题目要求两组都不能为空，因此正常情况下 n >= 2。# 这里增加保护处理，避免异常输入。ifn<2:print(0)return# 排序之后，最优划分可以看成在某两个相邻元素之间切分。nums.sort()# 分界处的相邻差不会计入任何一组内部的极差。# 因此，应当选择最大的相邻差作为分界位置。max_gap=max(nums[i+1]-nums[i]foriinrange(n-1))# 最小极差和 = 整体极差 - 最大相邻差answer=nums[-1]-nums[0]-max_gapprint(answer)if__name__=="__main__":main()

五、JavaScript算法源码

constfs=require('fs');constinput=fs.readFileSync(0,'utf8').trim();if(!input){process.exit(0);}consttokens=input.split(/\s+/);constn=Number(tokens[0]);constnums=[];for(leti=0;i<n;i++){// 使用 BigInt 保存整数，避免 Number 超过安全整数范围后产生精度问题。nums.push(BigInt(tokens[i+1]));}if(n<2){console.log('0');process.exit(0);}/* * BigInt 不能通过 (a, b) => a - b 直接作为 sort 比较器， * 因为比较器要求返回 Number。 * 因此通过大小关系返回 -1、0、1。 */nums.sort((a,b)=>{if(a<b)return-1;if(a>b)return1;return0;});letmaxGap=0n;for(leti=0;i<n-1;i++){/* * 如果在 nums[i] 和 nums[i + 1] 之间切分， * 这一段距离不会计入任何一组的极差。 * 因此寻找最大的相邻差作为分界。 */constgap=nums[i+1]-nums[i];if(gap>maxGap){maxGap=gap;}}// 最小极差和 = 整体极差 - 最大相邻差constanswer=nums[n-1]-nums[0]-maxGap;console.log(answer.toString());

六、C算法源码

#include<stdio.h>#include<stdlib.h>/* * qsort 的比较函数。 * 不直接返回 x - y，因为 long long 的差值转换成 int 时可能溢出。 */staticintcmpLongLong(constvoid*a,constvoid*b){longlongx=*(constlonglong*)a;longlongy=*(constlonglong*)b;return(x>y)-(x<y);}intmain(void){intn;if(scanf("%d",&n)!=1){return0;}longlong*nums=(longlong*)malloc(sizeof(longlong)*(size_t)n);if(nums==NULL&&n>0){return0;}for(inti=0;i<n;++i){scanf("%lld",&nums[i]);}// 题目正常输入满足 n >= 2，这里进行异常输入保护。if(n<2){printf("0\n");free(nums);return0;}/* * 排序后，只需要寻找最大的相邻差。 * 最大相邻差所在位置就是最优的两组分界位置。 */qsort(nums,(size_t)n,sizeof(longlong),cmpLongLong);longlongmaxGap=0;for(inti=0;i<n-1;++i){longlonggap=nums[i+1]-nums[i];if(gap>maxGap){maxGap=gap;}}// 最小极差和 = 整体极差 - 最大相邻差longlonganswer=nums[n-1]-nums[0]-maxGap;printf("%lld\n",answer);free(nums);return0;}

七、C++算法源码

#include<algorithm>#include<iostream>#include<vector>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cin>>n)){return0;}vector<longlong>nums(n);for(auto&x:nums){cin>>x;}// 正常数据满足 n >= 2，这里保留保护逻辑。if(n<2){cout<<0<<'\n';return0;}/* * 排序后，最优划分一定可以在两个相邻元素之间完成。 * 因此只需要寻找最大的相邻差。 */sort(nums.begin(),nums.end());longlongmaxGap=0;for(inti=0;i<n-1;++i){/* * 最大相邻差作为分界线时， * 可以从整体极差中“去掉”最大的那一段距离。 */maxGap=max(maxGap,nums[i+1]-nums[i]);}// 最小极差和 = 整体极差 - 最大相邻差longlonganswer=nums.back()-nums.front()-maxGap;cout<<answer<<'\n';return0;}

八、Go算法源码

packagemainimport("bufio""fmt""os""sort")funcmain(){in:=bufio.NewReader(os.Stdin)out:=bufio.NewWriter(os.Stdout)deferout.Flush()varnintif_,err:=fmt.Fscan(in,&n);err!=nil{return}nums:=make([]int64,n)fori:=0;i<n;i++{fmt.Fscan(in,&nums[i])}// 题目正常输入满足 n >= 2，这里进行保护处理。ifn<2{fmt.Fprintln(out,0)return}/* 排序后，最优方案可以看成： 在某两个相邻元素之间切分， 左边构成一组，右边构成另一组。 */sort.Slice(nums,func(i,jint)bool{returnnums[i]<nums[j]})varmaxGapint64=0fori:=0;i<n-1;i++{/* 分界位置的相邻距离不会计入任意一组的极差， 因此找到最大的相邻差作为分界即可。 */gap:=nums[i+1]-nums[i]ifgap>maxGap{maxGap=gap}}// 最小极差和 = 整体极差 - 最大相邻差answer:=nums[n-1]-nums[0]-maxGap fmt.Fprintln(out,answer)}