按序分苹果

华为笔试真题 10月23号 第一题 100分题型

题目内容

园长阿姨手里捧着AAA个苹果，分量各不相同，从左到右的重量记作g1,g2,…,gAg_1, g_2, \ldots, g_Ag1​,g2​,…,gA​。班里有BBB个小朋友，按学号从前往后站成一行。这些苹果要顺着站位发下去，规则有两条：

1. 不许剩下：每个人至少领一个，苹果也要全部发出去。
2. 尽量匀一些：每个人领到的分量之和要彼此靠近。
   请给出一个最小的数。它是所有发法里，各人拿到的总重量中最大的那一份，再把这个最大份压到最低。
   换句话说，每种发法先记下最沉的那一份，再在这些记录当中取最小的一个。
   苹果必须维持现在的左右次序，只能从左往右切成BBB段连续苹果。第111段交给站在最前的小朋友，后面各段按站位依次往后交。不相邻的苹果不能抽出来交给同一个人。
   举个小例子。三个苹果重量是2,5,12, 5, 12,5,1，发给222个小朋友。切成[2][2][2]与[5,1][5, 1][5,1]，两份是222和666，最沉的是666；切成[2,5][2, 5][2,5]与[1][1][1]，两份是777和111，最沉的是777。所以最低能压到666。

输入描述

• 第一行给出两个整数AAA和BBB。AAA是苹果有多少个，BBB是小朋友有多少人。
• 第二行给出AAA个整数g1,g2,…,gAg_1, g_2, \ldots, g_Ag1​,g2​,…,gA​，按从左到右的次序写每个苹果的重量。
  数据范围：
• 1≤A≤1031 \le A \le 10^31≤A≤103
• 1≤B≤A1 \le B \le A1≤B≤A
• 1≤gt≤1021 \le g_t \le 10^21≤gt​≤102

输出描述

只写出一个整数，表示最沉那一份能够压到的最小重量。

样例1

输入

4 3 4 1 5 2

输出

5

说明
要切成333段，只能在相邻苹果之间下刀。

• [4] [1] [5,2][4]\ [1]\ [5, 2][4][1][5,2]，三份是444、111、777，最沉777。
• [4] [1,5] [2][4]\ [1, 5]\ [2][4][1,5][2]，三份是444、666、222，最沉666。
• [4,1] [5] [2][4, 1]\ [5]\ [2][4,1][5][2]，三份是555、555、222，最沉555。
  最低能压到555，对应最后一种切法。

样例2

输入

5 2 3 6 1 4 2

输出

9

说明
切成222段时，下刀的位置只有四种：

• [3][3][3]与后面，333和131313，最沉131313。
• [3,6][3, 6][3,6]与后面，999和777，最沉999。
• [3,6,1][3, 6, 1][3,6,1]与后面，101010和666，最沉101010。
• [3,6,1,4][3, 6, 1, 4][3,6,1,4]与后面，141414和222，最沉141414。
  四种里最沉份的最小值是999。

题解和思路

思路

实现思路：二分

1. 如果限制每段最大重量不超x，判断苹果是否能分成B段。如果x可行，那么限制为大于x的肯定可行，反之小于x不一定可行，因此具备单调性，可采用二分进行求解。
2. 二分上下界确定，题目要求每段必须分配一个苹果，那么left = max(g), 同时所有苹果存在分配给一个小朋友情况，那么right = sum(g), 每次枚举中间值mid = (left + right) /2作为限制值，判断是否可行，根据判断结果更新上下界，直到left = right结束
   • 不可行：更新left = mid + 1
   • 可行：更新right = mid
3. 判断指定x是否可行采用贪心，从前往后进行分割，每个小朋友分配不大于x的重量，判断所需小朋友数量是否小于等于B。
4. 算法总体时间复杂度为O(AlogS)

C++

#include<bits/stdc++.h>usingnamespacestd;intA,B;vector<int>g;boolcheck(intt){intcnt=1;intsum=0;for(inti=0;i<A;i++){if(g[i]>t){returnfalse;}if(sum+g[i]<=t){sum+=g[i];}else{cnt++;sum=g[i];}}returncnt<=B;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>A>>B;g.resize(A);intleft=0;intright=0;for(inti=0;i<A;i++){cin>>g[i];left=max(left,g[i]);right+=g[i];}// 枚举分到的最大值不超midwhile(left<right){intmid=(left+right)>>1;if(check(mid)){right=mid;}else{left=mid+1;}}cout<<left;return0;}

Java

importjava.util.Scanner;publicclassMain{staticintA,B;staticint[]g;staticbooleancheck(intt){intcnt=1;intsum=0;for(inti=0;i<A;i++){if(g[i]>t){returnfalse;}if(sum+g[i]<=t){sum+=g[i];}else{cnt++;sum=g[i];}}returncnt<=B;}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);A=sc.nextInt();B=sc.nextInt();g=newint[A];intleft=0;intright=0;for(inti=0;i<A;i++){g[i]=sc.nextInt();left=Math.max(left,g[i]);right+=g[i];}// 枚举分到的最大值不超 midwhile(left<right){intmid=(left+right)>>1;if(check(mid)){right=mid;}else{left=mid+1;}}System.out.println(left);sc.close();}}

python

importsys A,B=map(int,sys.stdin.readline().split())g=list(map(int,sys.stdin.readline().split()))defcheck(t):cnt=1total=0foriinrange(A):ifg[i]>t:returnFalseiftotal+g[i]<=t:total+=g[i]else:cnt+=1total=g[i]returncnt<=B left=max(g)right=sum(g)# 枚举分到的最大值不超 midwhileleft<right:mid=(left+right)>>1ifcheck(mid):right=midelse:left=mid+1print(left)

Javascript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on('line',(line)=>{input.push(...line.trim().split(/\s+/).filter(Boolean));});rl.on('close',()=>{letidx=0;constA=Number(input[idx++]);constB=Number(input[idx++]);constg=[];letleft=0;letright=0;for(leti=0;i<A;i++){g[i]=Number(input[idx++]);left=Math.max(left,g[i]);right+=g[i];}functioncheck(t){letcnt=1;letsum=0;for(leti=0;i<A;i++){if(g[i]>t){returnfalse;}if(sum+g[i]<=t){sum+=g[i];}else{cnt++;sum=g[i];}}returncnt<=B;}// 枚举分到的最大值不超 midwhile(left<right){constmid=Math.floor((left+right)/2);if(check(mid)){right=mid;}else{left=mid+1;}}console.log(left);});

Go

packagemainimport("bufio""fmt""os")varA,Bintvarg[]intfunccheck(tint)bool{cnt:=1sum:=0fori:=0;i<A;i++{ifg[i]>t{returnfalse}ifsum+g[i]<=t{sum+=g[i]}else{cnt++sum=g[i]}}returncnt<=B}funcmain(){reader:=bufio.NewReader(os.Stdin)writer:=bufio.NewWriter(os.Stdout)deferwriter.Flush()fmt.Fscan(reader,&A,&B)g=make([]int,A)left:=0right:=0fori:=0;i<A;i++{fmt.Fscan(reader,&g[i])ifg[i]>left{left=g[i]}right+=g[i]}// 枚举分到的最大值不超 midforleft<right{mid:=(left+right)>>1ifcheck(mid){right=mid}else{left=mid+1}}fmt.Fprintln(writer,left)}