末世分配资源包(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 kk（1 ≤ 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
题解
思路：二分 + 贪心
这种
在...条件下，求最值的基本都是是二分的套路题。见到这种题可以优先考虑二分算法进行处理。首先确定上下边界
- 下边界很容易想到为所有资源的最大值。
- 上边界为所有资源总和，当
k==1的会选择。
确定好上下边界时，每轮枚举上下边界中间值
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++
#include<bits/stdc++.h>#include<vector>usingnamespacestd;// 通用 切割函数 函数 将字符串str根据delimiter进行切割vector<int>split(conststring&str,conststring&delimiter){vector<int>result;size_t start=0;size_t end=str.find(delimiter);while(end!=string::npos){result.push_back(stoi(str.substr(start,end-start)));start=end+delimiter.length();end=str.find(delimiter,start);}// 添加最后一个部分result.push_back(stoi(str.substr(start)));returnresult;}intsolve(vector<int>&nums,intk){intn=nums.size();if(n==0){return0;}intleft,right;left=right=0;// 确定二分边界for(inti=0;i<n;i++){// 下边界为最大资源left=max(left,nums[i]);// 上边界为资源总和right+=nums[i];}while(left<right){intmid=(left+right)>>1;// 贪心计算分段数intcount=1;intsum=0;for(inti=0;i<n;i++){if(sum+nums[i]>mid){count++;sum=nums[i];}else{sum+=nums[i];}}// 值刚好或者值太大，尝试更小值if(count<=k){right=mid;// 值太小，应该升高}else{left=mid+1;}}returnleft;}intmain(){string input1;getline(cin,input1);intk;cin>>k;vector<int>nums=split(input1,",");cout<<solve(nums,k);return0;}JAVA
importjava.io.*;importjava.util.*;publicclassMain{staticintsolve(int[]nums,intk){intn=nums.length;if(n==0){return0;}intleft=0;intright=0;// 确定二分边界for(inti=0;i<n;i++){// 下边界为最大资源left=Math.max(left,nums[i]);// 上边界为资源总和right+=nums[i];}while(left<right){intmid=(left+right)>>1;// 贪心计算分段数intcount=1;intsum=0;for(inti=0;i<n;i++){if(sum+nums[i]>mid){count++;sum=nums[i];}else{sum+=nums[i];}}// 值刚好或者值太大，尝试更小值if(count<=k){right=mid;// 值太小，应该升高}else{left=mid+1;}}returnleft;}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));Stringinput1=br.readLine();intk=Integer.parseInt(br.readLine().trim());String[]parts=input1.split(",");int[]nums=newint[parts.length];for(inti=0;i<parts.length;i++){nums[i]=Integer.parseInt(parts[i].trim());}System.out.print(solve(nums,k));}}Python
defsolve(nums,k):n=len(nums)ifn==0:return0left=0right=0# 确定二分边界foriinrange(n):# 下边界为最大资源left=max(left,nums[i])# 上边界为资源总和right+=nums[i]whileleft<right:mid=(left+right)>>1# 贪心计算分段数count=1sum_val=0foriinrange(n):ifsum_val+nums[i]>mid:count+=1sum_val=nums[i]else:sum_val+=nums[i]# 值刚好或者值太大，尝试更小值ifcount<=k:right=mid# 值太小，应该升高else:left=mid+1returnleft input1=input()k=int(input())nums=list(map(int,input1.split(",")))print(solve(nums,k),end="")JavaScript
constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinputs=[];rl.on('line',line=>{inputs.push(line);});rl.on('close',()=>{constinput1=inputs[0];constk=parseInt(inputs[1]);constnums=input1.split(',').map(Number);console.log(solve(nums,k));});functionsolve(nums,k){constn=nums.length;if(n===0){return0;}letleft=0;letright=0;// 确定二分边界for(leti=0;i<n;i++){// 下边界为最大资源left=Math.max(left,nums[i]);// 上边界为资源总和right+=nums[i];}while(left<right){constmid=Math.floor((left+right)/2);// 贪心计算分段数letcount=1;letsum=0;for(leti=0;i<n;i++){if(sum+nums[i]>mid){count++;sum=nums[i];}else{sum+=nums[i];}}// 值刚好或者值太大，尝试更小值if(count<=k){right=mid;// 值太小，应该升高}else{left=mid+1;}}returnleft;}Go
packagemainimport("bufio""fmt""os""strconv""strings")funcsolve(nums[]int,kint)int{n:=len(nums)ifn==0{return0}left:=0right:=0// 确定二分边界fori:=0;i<n;i++{// 下边界为最大资源ifnums[i]>left{left=nums[i]}// 上边界为资源总和right+=nums[i]}forleft<right{mid:=(left+right)>>1// 贪心计算分段数count:=1sum:=0fori:=0;i<n;i++{ifsum+nums[i]>mid{count++sum=nums[i]}else{sum+=nums[i]}}// 值刚好或者值太大，尝试更小值ifcount<=k{right=mid// 值太小，应该升高}else{left=mid+1}}returnleft}funcmain(){in:=bufio.NewReader(os.Stdin)out:=bufio.NewWriter(os.Stdout)deferout.Flush()input1,_:=in.ReadString('\n')input2,_:=in.ReadString('\n')input1=strings.TrimSpace(input1)input2=strings.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语言
#include<stdio.h>#include<stdlib.h>#include<string.h>intsolve(int*nums,intn,intk){if(n==0){return0;}intleft=0;intright=0;// 确定二分边界for(inti=0;i<n;i++){// 下边界为最大资源if(nums[i]>left){left=nums[i];}// 上边界为资源总和right+=nums[i];}while(left<right){intmid=(left+right)>>1;// 贪心计算分段数intcount=1;intsum=0;for(inti=0;i<n;i++){if(sum+nums[i]>mid){count++;sum=nums[i];}else{sum+=nums[i];}}// 值刚好或者值太大，尝试更小值if(count<=k){right=mid;// 值太小，应该升高}else{left=mid+1;}}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);intn=0;// 使用strtok按逗号切割char*token=strtok(input1,",");while(token!=NULL){nums[n++]=atoi(token);token=strtok(NULL,",");}intk=atoi(input2);printf("%d",solve(nums,n,k));free(nums);return0;}
