8.12华为OD机试真题 新系统 - 末世分配资源包 (Java/Py/C/C++/Js/Go)

末世分配资源包2026 华为OD机试真题8月12日华为OD上机新系统考试真题 100 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解题目描述末世时代政府为各地分配资源现有资源分配表nums[n]要求按如下规则分配给 k 个营地每个营地只分配一段连续的分配表每个营地至少分到一份资源所有的资源必须全部分出分配方式尽量平均分配即得利最大的营地获得的资源值尽量小输入描述资源存储数组nums[n]资源数 n: 0≤n≤1000每份资源数1≤nums[i]≤100000营地数 k1≤k≤min(50,n)输入为两行nums k其中nums为英文逗号分隔的整数数组。输出描述在最优平均分配情况下得利最大团队所获得的资源数示例1输入4,3,6,9,7 2输出16说明可能的切分[4],[3,6,9,7]最大值25[4,3],[6,9,7]最大值22[4,3,6],[9,7]最大值16[4,3,6,9],[7]最大值22因此最大值最小的切分方式是第3种返回16示例2输入3,4,2,1 4输出4说明可能的切分[3],[4],[2],[1]最大值4因此最大值最小的切分方式是第1种返回4解题思路核心思想题目要求把数组切成k段连续子数组并让所有段中最大的段和尽可能小。如果给定一个最大允许段和limit可以从左到右贪心分段当前段能继续放就继续放放不下就新开一段。这样得到的段数是该limit下所需的最少段数。若最少段数 k说明limit足够大可以尝试更小的最大段和否则说明limit太小需要增大。因此可以对答案做二分查找。算法步骤答案下界为max(nums)因为任何一段至少要容纳一个资源包。答案上界为sum(nums)表示所有资源包分给一个营地。二分枚举最大段和mid。使用贪心统计在每段和不超过mid时至少需要多少段。如果段数 k说明可行缩小右边界否则增大左边界。二分结束后left即为最小可能的最大段和。复杂度分析设数组长度为n所有资源包总和为S。时间复杂度O(n log S)空间复杂度O(1)Javaimportjava.util.*;publicclassMain{publicstaticintsolve(int[]nums,intk){intleft0;intright0;for(intnum:nums){// 答案至少要能容纳最大的单个资源包leftMath.max(left,num);rightnum;}while(leftright){intmidleft(right-left)/2;intsegments1;intcurrentSum0;for(intnum:nums){// 当前段放不下时新开一个营地分段if(currentSumnummid){segments;currentSumnum;}else{currentSumnum;}}// 最少段数不超过 k说明还可以尝试更小的最大段和if(segmentsk){rightmid;}else{leftmid1;}}returnleft;}publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);StringnumsLinescanner.nextLine().trim();intkInteger.parseInt(scanner.nextLine().trim());String[]partsnumsLine.split(,);int[]numsnewint[parts.length];for(inti0;iparts.length;i){nums[i]Integer.parseInt(parts[i].trim());}System.out.println(solve(nums,k));}}Pythondefsolve(nums,k):leftmax(nums)rightsum(nums)whileleftright:mid(leftright)//2segments1current_sum0fornuminnums:# 当前段超过限制时新开一个营地分段ifcurrent_sumnummid:segments1current_sumnumelse:current_sumnum# 最少段数不超过 k说明该最大段和可行ifsegmentsk:rightmidelse:leftmid1returnleft numslist(map(int,input().strip().split(,)))kint(input().strip())print(solve(nums,k))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,line{lines.push(line.trim());});rl.on(close,(){constnumslines[0].split(,).map(Number);constkNumber(lines[1]);console.log(solve(nums,k));});functionsolve(nums,k){letleftMath.max(...nums);letrightnums.reduce((sum,num)sumnum,0);while(leftright){constmidMath.floor((leftright)/2);letsegments1;letcurrentSum0;for(constnumofnums){// 当前营地放不下时新开一个连续分段if(currentSumnummid){segments;currentSumnum;}else{currentSumnum;}}// 可用段数不超过 k 时继续压缩最大段和if(segmentsk){rightmid;}else{leftmid1;}}returnleft;}C#includebits/stdc.husingnamespacestd;intsolve(constvectorintnums,intk){intleft0;intright0;for(intnum:nums){// 下界是最大的单个资源包上界是全部资源总和leftmax(left,num);rightnum;}while(leftright){intmidleft(right-left)/2;intsegments1;intcurrentSum0;for(intnum:nums){// 超过当前限制则开启新的营地分段if(currentSumnummid){segments;currentSumnum;}else{currentSumnum;}}// 段数不超过 k 表示当前限制可行if(segmentsk){rightmid;}else{leftmid1;}}returnleft;}vectorintparseNums(conststringline){vectorintnums;string item;stringstreamss(line);while(getline(ss,item,,)){nums.push_back(stoi(item));}returnnums;}intmain(){string numsLine;string kLine;getline(cin,numsLine);getline(cin,kLine);vectorintnumsparseNums(numsLine);intkstoi(kLine);coutsolve(nums,k)endl;return0;}Gopackagemainimport(bufiofmtosstrconvstrings)funcsolve(nums[]int,kint)int{left,right:0,0for_,num:rangenums{// 答案范围由最大单个资源包和资源总和确定ifnumleft{leftnum}rightnum}forleftright{mid:left(right-left)/2segments:1currentSum:0for_,num:rangenums{// 当前连续段超过限制时新开一段ifcurrentSumnummid{segmentscurrentSumnum}else{currentSumnum}}// 最少段数不超过 k说明该限制可行ifsegmentsk{rightmid}else{leftmid1}}returnleft}funcmain(){reader:bufio.NewReader(os.Stdin)numsLine,_:reader.ReadString(\n)kLine,_:reader.ReadString(\n)parts:strings.Split(strings.TrimSpace(numsLine),,)nums:make([]int,len(parts))fori,part:rangeparts{nums[i],_strconv.Atoi(strings.TrimSpace(part))}k,_:strconv.Atoi(strings.TrimSpace(kLine))fmt.Println(solve(nums,k))}C语言#includestdio.h#includestdlib.h#includestring.hintsolve(intnums[],intn,intk){intleft0;intright0;for(inti0;in;i){// 二分下界为最大资源包上界为资源总和if(nums[i]left){leftnums[i];}rightnums[i];}while(leftright){intmidleft(right-left)/2;intsegments1;intcurrentSum0;for(inti0;in;i){// 当前段无法继续放入资源包时新开一段if(currentSumnums[i]mid){segments;currentSumnums[i];}else{currentSumnums[i];}}// 所需最少段数不超过 k则当前最大段和可行if(segmentsk){rightmid;}else{leftmid1;}}returnleft;}intmain(){charline[10000];intk;intnums[1000];intn0;fgets(line,sizeof(line),stdin);scanf(%d,k);char*tokenstrtok(line,,\r\n);while(token!NULL){nums[n]atoi(token);tokenstrtok(NULL,,\r\n);}printf(%d\n,solve(nums,n,k));return0;}完整用例用例14,3,6,9,7 2用例23,4,2,1 4用例310 1用例41,2,3,4,5 2用例57,2,5,10,8 2用例61,1,1,1,1 3用例7100000,100000,100000 2用例89,8,7,6,5 3用例92,3,1,2,4,3 5用例105,5,5,5 1文章目录**末世分配资源包**题目描述输入描述输出描述示例1示例2解题思路核心思想算法步骤复杂度分析JavaPythonJavaScriptCGoC语言完整用例用例1用例2用例3用例4用例5用例6用例7用例8用例9用例10