末世分配资源包(Java /C/Py/Js/Go/C)题解华为OD机试新系统真题 华为OD上机考试新系统真题 8月12号 200分题型华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录机考题库 算法考点详解题目内容末世时代政府为各地分配资源现有资源分配表nums[n]要求按如下规则分配给k kk个营地每个营地只分配一段连续的分配表每个营地至少分到一份资源所有的资源必须全部分出分配方式尽量平均分配即得利最大的营地获得的资源值尽量小输入描述资源存储数组nums[n]资源数n nn:0 ≤ n ≤ 1000 0 \le n \le 10000≤n≤1000每份资源数1 ≤ n u m s [ i ] ≤ 100000 1 \le nums[i] \le 1000001≤nums[i]≤100000营地数k kk1 ≤ k ≤ min ⁡ ( 50 , n ) 1 \le k \le \min(50, n)1≤k≤min(50,n)输出描述在最优平均分配情况下得利最大团队所获得的资源数样例1输入4,3,6,9,7 2输出16说明可能的切分[4],[3,6,8,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题解思路二分 贪心这种在...条件下求最值的基本都是是二分的套路题。见到这种题可以优先考虑二分算法进行处理。首先确定上下边界下边界很容易想到为所有资源的最大值。上边界为所有资源总和当k1的会选择。确定好上下边界时每轮枚举上下边界中间值mid (left right) /2, 并判断在每组资源总数不超过mid下分配组数和k的关系并按照大小关系更新上下边界直到left right时结束。更新上下边界规律如下分配组数 k说明mid值刚好或者值太大此时可以尝试更新值更新right mid分配组数 k, 说明mid值太小必须尝试更达至更新left mid 1在mid限制求解可分配组数采用贪心进行求解使用sum记录当前组总和cnt记录已分配组数量从前往后遍历nums当sum nums[i] mid说明该组无法继续容纳当前资源需要重新分配一个组更新cnt, sum nums[i]当sum nums[i] mid说明该组可以继续容纳当前资源更新sum nums[i]C#includebits/stdc.h#includevectorusingnamespacestd;// 通用 切割函数 函数 将字符串str根据delimiter进行切割vectorintsplit(conststringstr,conststringdelimiter){vectorintresult;size_t start0;size_t endstr.find(delimiter);while(end!string::npos){result.push_back(stoi(str.substr(start,end-start)));startenddelimiter.length();endstr.find(delimiter,start);}// 添加最后一个部分result.push_back(stoi(str.substr(start)));returnresult;}intsolve(vectorintnums,intk){intnnums.size();if(n0){return0;}intleft,right;leftright0;// 确定二分边界for(inti0;in;i){// 下边界为最大资源leftmax(left,nums[i]);// 上边界为资源总和rightnums[i];}while(leftright){intmid(leftright)1;// 贪心计算分段数intcount1;intsum0;for(inti0;in;i){if(sumnums[i]mid){count;sumnums[i];}else{sumnums[i];}}// 值刚好或者值太大尝试更小值if(countk){rightmid;// 值太小应该升高}else{leftmid1;}}returnleft;}intmain(){string input1;getline(cin,input1);intk;cink;vectorintnumssplit(input1,,);coutsolve(nums,k);return0;}JAVAimportjava.io.*;importjava.util.*;publicclassMain{staticintsolve(int[]nums,intk){intnnums.length;if(n0){return0;}intleft0;intright0;// 确定二分边界for(inti0;in;i){// 下边界为最大资源leftMath.max(left,nums[i]);// 上边界为资源总和rightnums[i];}while(leftright){intmid(leftright)1;// 贪心计算分段数intcount1;intsum0;for(inti0;in;i){if(sumnums[i]mid){count;sumnums[i];}else{sumnums[i];}}// 值刚好或者值太大尝试更小值if(countk){rightmid;// 值太小应该升高}else{leftmid1;}}returnleft;}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));Stringinput1br.readLine();intkInteger.parseInt(br.readLine().trim());String[]partsinput1.split(,);int[]numsnewint[parts.length];for(inti0;iparts.length;i){nums[i]Integer.parseInt(parts[i].trim());}System.out.print(solve(nums,k));}}Pythondefsolve(nums,k):nlen(nums)ifn0:return0left0right0# 确定二分边界foriinrange(n):# 下边界为最大资源leftmax(left,nums[i])# 上边界为资源总和rightnums[i]whileleftright:mid(leftright)1# 贪心计算分段数count1sum_val0foriinrange(n):ifsum_valnums[i]mid:count1sum_valnums[i]else:sum_valnums[i]# 值刚好或者值太大尝试更小值ifcountk:rightmid# 值太小应该升高else:leftmid1returnleft input1input()kint(input())numslist(map(int,input1.split(,)))print(solve(nums,k),end)JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinputs[];rl.on(line,line{inputs.push(line);});rl.on(close,(){constinput1inputs[0];constkparseInt(inputs[1]);constnumsinput1.split(,).map(Number);console.log(solve(nums,k));});functionsolve(nums,k){constnnums.length;if(n0){return0;}letleft0;letright0;// 确定二分边界for(leti0;in;i){// 下边界为最大资源leftMath.max(left,nums[i]);// 上边界为资源总和rightnums[i];}while(leftright){constmidMath.floor((leftright)/2);// 贪心计算分段数letcount1;letsum0;for(leti0;in;i){if(sumnums[i]mid){count;sumnums[i];}else{sumnums[i];}}// 值刚好或者值太大尝试更小值if(countk){rightmid;// 值太小应该升高}else{leftmid1;}}returnleft;}Gopackagemainimport(bufiofmtosstrconvstrings)funcsolve(nums[]int,kint)int{n:len(nums)ifn0{return0}left:0right:0// 确定二分边界fori:0;in;i{// 下边界为最大资源ifnums[i]left{leftnums[i]}// 上边界为资源总和rightnums[i]}forleftright{mid:(leftright)1// 贪心计算分段数count:1sum:0fori:0;in;i{ifsumnums[i]mid{countsumnums[i]}else{sumnums[i]}}// 值刚好或者值太大尝试更小值ifcountk{rightmid// 值太小应该升高}else{leftmid1}}returnleft}funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()input1,_:in.ReadString(\n)input2,_:in.ReadString(\n)input1strings.TrimSpace(input1)input2strings.TrimSpace(input2)parts:strings.Split(input1,,)nums:make([]int,len(parts))fori,s:rangeparts{nums[i],_strconv.Atoi(strings.TrimSpace(s))}k,_:strconv.Atoi(input2)fmt.Fprint(out,solve(nums,k))}C语言#includestdio.h#includestdlib.h#includestring.hintsolve(int*nums,intn,intk){if(n0){return0;}intleft0;intright0;// 确定二分边界for(inti0;in;i){// 下边界为最大资源if(nums[i]left){leftnums[i];}// 上边界为资源总和rightnums[i];}while(leftright){intmid(leftright)1;// 贪心计算分段数intcount1;intsum0;for(inti0;in;i){if(sumnums[i]mid){count;sumnums[i];}else{sumnums[i];}}// 值刚好或者值太大尝试更小值if(countk){rightmid;// 值太小应该升高}else{leftmid1;}}returnleft;}intmain(){charinput1[10000];charinput2[100];fgets(input1,sizeof(input1),stdin);fgets(input2,sizeof(input2),stdin);// 去除换行符input1[strcspn(input1,\r\n)]\0;input2[strcspn(input2,\r\n)]\0;int*nums(int*)malloc(sizeof(int)*10000);intn0;// 使用strtok按逗号切割char*tokenstrtok(input1,,);while(token!NULL){nums[n]atoi(token);tokenstrtok(NULL,,);}intkatoi(input2);printf(%d,solve(nums,n,k));free(nums);return0;}​