华为OD新系统真题-最小极差分组(C/C++/Py/Java/Js/Go)

最小极差分组华为OD机试新系统真题 华为OD上机考试新系统真题 6月28号 100分题型华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录机考题库 算法考点详解题目内容给定n nn个整数你需要将它们任意分成两组且两组都不能为空。对于一组数它的极差定义为该组中的最大值减去最小值。设两组分别为第1 11组和第2 22组则它们的极差分别为第1 11组极差 第1 11组最大值− -−第1 11组最小值第2 22组极差 第2 22组最大值− -−第2 22组最小值你的目标是最小化这两个极差之和即最小化( max 1 − min 1 ) ( max 2 − min 2 ) (\text{max}1-\text{min}1)(\text{max}2-\text{min}2)(max1−min1)(max2−min2)请输出这个最小值。样例1输入5 10 1 5 3 8输出6说明划分为[ 10 , 8 ] [10,8][10,8]和[ 1 , 5 , 3 ] [1,5,3][1,5,3]两组左极差 5 55-1 11 4 44右极差 10 1010-8 88 2 22总和 6 66样例2输入5 1 1 9 1 9输出0说明分组为[ 1 , 1 , 1 ] [1,1,1][1,1,1]和[ 9 , 9 ] [9,9][9,9]两组的极差均为0 00和也为0 00样例3输入2 1 2输出0说明只能分为两组每组一个数。每组的最大最小值是同一个数极差为0 00。题解思路逻辑分析先对输入数组nums进行升序排序。接下来考虑两种情况最大值和最小值位于同一组nums[0], nums[n-1], 要想整体和最小另一组的max - min最小为0只包含一个数此时能够取得的极差为nums[n-1] - nums[0]最大值和最小值位于不同组中此时可以通过枚举切分点为i其中nums[i]和nums[0]位于同一组贡献极差为nums[i] - nums[0], 另一组能够贡献的极差达到最小,则需要[0....i]同属一组这种切分极差为nums[i] - nums[0] nums[n-1] - nums[i1]按照2逻辑进行枚举记录其中最小值就是结果。c#includebits/stdc.h#includevectorusingnamespacestd;longminGroupValue(intn,vectorintnums){// 升序排序sort(nums.begin(),nums.end());if(n2){return0;}// 最小值和最大值为同一组能够得到的最小极差longansnums[n-1]-nums[0];// 最小值和最大值不属于同一组情况枚举分割点for(inti0;in-1;i){longcostnums[i]-nums[0]nums[n-1]-nums[i1];if(costans){anscost;}}returnans;}intmain(){intn;cinn;vectorintnums(n);for(inti0;in;i){cinnums[i];}coutminGroupValue(n,nums);return0;}Javaimportjava.util.*;publicclassMain{publicstaticlongminGroupValue(intn,int[]nums){// 升序排序Arrays.sort(nums);if(n2){return0;}// 最小值和最大值为同一组能够得到的最小极差longans(long)nums[n-1]-nums[0];// 最小值和最大值不属于同一组情况枚举分割点for(inti0;in-1;i){longcost(long)nums[i]-nums[0](long)nums[n-1]-nums[i1];if(costans){anscost;}}returnans;}publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);intnscanner.nextInt();int[]numsnewint[n];for(inti0;in;i){nums[i]scanner.nextInt();}System.out.println(minGroupValue(n,nums));}}PythondefminGroupValue(n,nums):# 升序排序nums.sort()ifn2:return0# 最小值和最大值为同一组能够得到的最小极差ansnums[-1]-nums[0]# 最小值和最大值不属于同一组情况枚举分割点foriinrange(n-1):costnums[i]-nums[0]nums[-1]-nums[i1]ifcostans:anscostreturnans nint(input())numslist(map(int,input().split()))print(minGroupValue(n,nums))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,(line){input.push(line);});rl.on(close,(){letindex0;constnparseInt(input[index]);constnumsinput[index].split( ).map(Number);console.log(minGroupValue(n,nums).toString());});functionminGroupValue(n,nums){// 升序排序nums.sort((a,b)a-b);if(n2){return0;}// 最小值和最大值为同一组能够得到的最小极差letansnums[n-1]-nums[0];// 最小值和最大值不属于同一组情况枚举分割点for(leti0;in-1;i){constcostnums[i]-nums[0]nums[n-1]-nums[i1];if(costans){anscost;}}returnans;}Gopackagemainimport(fmtsort)funcminGroupValue(nint,nums[]int)int64{// 升序排序sort.Ints(nums)ifn2{return0}// 最小值和最大值为同一组能够得到的最小极差ans:int64(nums[n-1]-nums[0])// 最小值和最大值不属于同一组情况枚举分割点fori:0;in-1;i{cost:int64(nums[i]-nums[0]nums[n-1]-nums[i1])ifcostans{anscost}}returnans}funcmain(){varnintfmt.Scan(n)nums:make([]int,n)fori:0;in;i{fmt.Scan(nums[i])}fmt.Println(minGroupValue(n,nums))}C语言#includestdio.h#includestdlib.hintcmp(constvoid*a,constvoid*b){return(*(int*)a)-(*(int*)b);}longminGroupValue(intn,intnums[]){// 升序排序qsort(nums,n,sizeof(int),cmp);if(n2){return0;}// 最小值和最大值为同一组能够得到的最小极差longans(long)nums[n-1]-nums[0];// 最小值和最大值不属于同一组情况枚举分割点for(inti0;in-1;i){longcost(long)nums[i]-nums[0](long)nums[n-1]-nums[i1];if(costans){anscost;}}returnans;}intmain(){intn;scanf(%d,n);intnums[n];for(inti0;in;i){scanf(%d,nums[i]);}printf(%ld\n,minGroupValue(n,nums));return0;}