准备考华为OD机考的同学对“双机位C卷”这几个字应该都不会陌生。机考系统会要求你提前架好正面摄像头和第二机位手机从侧后方45度对准桌面和屏幕全程录像。我第一次考的时候光调摄像头角度就折腾了快二十分钟手忙脚乱。但说句实话比起设备调试真正决定能不能通过的是算法题。今天想聊的这道“快递投放问题”是C卷里比较有代表性的一道中等题用Java实现起来不算复杂但思路如果没梳理清楚很容易在二分边界上卡住。文章会从考试环境讲起再完整拆解题目、给出可直接运行的Java代码最后补上一波机考实战经验和踩坑记录适合正在准备华为OD机考、或者想研究OD机试题型和面经的同学参考。1. 华为OD机考与双机位先搞清楚考试环境1.1 双机位到底怎么回事华为OD机考对着装和操作环境有一定要求最直观的就是双机位监控。所谓“双机位”通常指两个摄像设备同时参与监控正面一个摄像头对着你本人侧面一个摄像头对着你的双手、键盘和屏幕。正面机位一般用笔记本电脑自带摄像头或者外接USB摄像头就能解决侧面机位一般要求使用手机或平板通过指定的“考生端”App或小程序扫码绑定后把画面实时回传。这里面有个很关键的细节第二机位的摆放不是随便拿手机支在桌上就行。考官要求侧后方45度左右、距离半米到一米五之间能同时拍到你的上半身、手部动作和完整的电脑屏幕。角度太正容易挡住屏幕反光角度太偏画面里只能看到你的侧脸不符合要求。稳妥的做法是先把手机架好打开摄像头预览自己在座位上模拟敲代码的姿势确认画面里双手、键盘、屏幕都在取景范围内再进入正式考试。手机支架我建议提前买一个能夹桌边的那种比用书本垫稳得多考试中途低头调手机会非常被动。还要注意手机在考试期间不能熄屏不少同学忘记关闭自动锁屏或者被来电打断导致第二机位画面中断。比较成熟的方案是考前把手机调到“勿扰模式”或“飞行模式WiFi”然后插上充电线。飞行模式能挡掉来电和通知WiFi保证网络和录像上传不受影响充电线保证几个小时不掉电。这个操作很普通但能避免掉很多考中出现的小事故。1.2 环境检查清单考前必做机考环境以“干净、安静、无遮挡”为标准。我整理了一份自己考前会过一遍的清单虽然不是官方的正式文件但按这个思路准备基本上能应对多数考场的要求。房间方面选光线充足且没有逆光的书桌背后不要有大窗户或强光源否则人脸在画面里是黑的。桌面只留电脑、鼠标、键盘和水杯其他东西全部收走。有些批次明确禁止草稿纸和笔有些允许具体以邮件或考试系统通知为准不确定的情况下我建议不准备直接在电脑上做临时备注。房间门可以关上提前和同住的人打好招呼考试时间段不要进房间避免有人声或者走动被判定为异常。电脑方面考试前关闭所有不必要的软件弹窗微信、QQ、Outlook这类即时通讯工具最好直接退出。有人习惯开着浏览器查代码考前也全部清掉只保留考试系统页面。摄像头和麦克风权限要提前授权有些浏览器会拦截进入考试页之后才弹权限确认框就会白白浪费几分钟。网络方面尽量用有线网或者稳定的WiFi如果网络闪断做题界面会有影响后面我会专门讲抢救办法。2. “快递投放”题目拆解这道题到底在考什么2.1 题目描述与数据模型“快递投放”这个题名在不同批次的C卷里表述可能不完全一样有的是“包裹分拣”有的是“货物运输”但剥掉外壳之后的核心模型是一致的。我以最常见的描述给你还原一遍自动化分拣线上有N件包裹按顺序经过投递口每件包裹的重量为w[i]。分拣员需要把相邻的若干件包裹打包成一个“投放批次”每个批次的总重量不能超过投放车的承重上限limit。现在公司最多允许安排K个批次完成所有包裹的投放问承载上限limit至少设置为多少才能保证用不超过K个批次装完所有包裹换一种更技术的说法给定数组w最多分成K个连续子数组求所有子数组和的最大值中最小的那个是多少。这就是经典的“最小化最大子段和”问题LeetCode 410就是同款。输入输出格式一般是这样的输入 5 2 7 2 5 10 8 输出 18数组[7,2,5,10,8]K2最优切法是把[7,2,5]放在一个批次[10,8]放在另一个批次两个批次重量分别是14和18答案就是18。如果用别的方式切比如[7,2,5,10]和[8]最大段是24不如18。2.2 先避开一个常见误区很多同学拿到题的第一反应是“总共K段那把总和除以K得到平均值每段尽量往平均值上凑不就行了”。这个思路大方向没有错但包裹顺序是固定的单个包裹又不能拆开你没法让每一段都精确落在平均值附近。如果你直接随便定一个上限从左到右去切切出来的段数可能超过K也可能已经能装下却提前切了导致最大段变大。上限定多少本身就需要搜索。举个例子w[3,2,5,4]K2。总和是14平均值是7。如果以7作为上限从左到右切325549超过7所以段1是[3,2]段2是[5]不对547段2只能单独[5]段3是[4]一共3段超过了K。那把上限提到8呢32510超过8还是切[3,2]、[5]、[4]仍然是3段。再把上限提到932510超过9段1是[3,2]段2是[5,4]正好2段最大段和是9。所以答案其实是9而不是平均值7。这一步就很关键上限7和8都不行9才可行最优值需要在一定范围内逐个尝试或者聪明地搜索。2.3 二分答案的推导过程既然“上限定多少”需要搜索那能不能高效搜索能。注意一个性质当上限limit增大时在“每段重量不超过limit”的前提下最少需要的段数一定不会变多。因为上限越大每个批次能装的东西越多自然可以用更少的批次。反过来上限越小段数一定越多。这个性质叫单调性有了单调性就可以用二分答案。具体思路是这样的先确定答案落在哪个区间里。下限是数组中的最大值max(w)因为重达max的那件包裹无论怎么切至少需要一个批次单独承载它上限是数组总和sum(w)因为把所有包裹放进一个批次也满足约束。然后在这个区间里二分查找第一个“可行”的值也就是使所需段数不超过K的最小limit。判断某个limit是否可行用贪心从左到右切当前批次累积重量cur遇到下一个包裹w如果curw仍然不超过limit就继续放进当前批次如果超过就新开一个批次让当前包裹作为新批次的第一个。这种“能装就装装不下才换”的切法是给定上限时能得到最少段数的切法因为切得越晚前面的批次装得越满留给后面的包裹就越少段数不可能更多。这个贪心是安全的。我用上面那个[3,2,5,4]K2的例字走一遍二分流程left5right14。mid9check发现最少2段可行于是right9尝试更小的值。new left5,right9,mid7check发现最少3段不可行于是left8。new left8,right9,mid8check发现最少3段不可行于是left9。leftright9输出答案9。整个思考链条是这样的先看懂题面要求什么发现是“限制一个上限判断段数是否够用”再发现“段数随上限单调变化”最后决定二分去查找最小可行值。这就是二分答案的标准套路。3. Java实现直接能跑的完整代码3.1 OD机考的Java输入输出模板华为OD机考使用Java提交时一般要求写一个Main类从标准输入读取数据把结果打印到标准输出。这个和平时刷LeetCode只需要填函数体不太一样很多同学第一次上机就挂在输入输出上。读取部分直接用Scanner就够了。第一行通常是两个整数n和k第二行是n个整数。Scanner的nextInt方法会跳过空格和换行所以不管是单行还是多行输入都能处理。输出部分用System.out.println题目要求输出一个整数就只输出这个整数不要画蛇添足打印别的提示信息。类名一定要是Main如果你写成Test或者别的名字云端编译会直接报错。3.2 完整代码下面是这道“快递投放问题”的完整Java实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); int[] w new int[n]; long sum 0; int max 0; for (int i 0; i n; i) { w[i] sc.nextInt(); sum w[i]; if (w[i] max) { max w[i]; } } long left max; long right sum; while (left right) { long mid left (right - left) / 2; if (canSplit(w, k, mid)) { right mid; } else { left mid 1; } } System.out.println(left); sc.close(); } private static boolean canSplit(int[] w, int k, long limit) { int segments 1; long current 0; for (int weight : w) { if (current weight limit) { segments; current weight; if (segments k) { return false; } } else { current weight; } } return true; } }这段代码唯一需要注意的地方是sum、left、right、mid、current这些变量都用了long而不是int。因为数组长度和数据范围大的时候总和可能超过int上限int会溢出变成负数二分直接乱掉。这是华为OD机考里非常容易踩的一个雷。3.3 关键代码逐段讲解二分部分用的是“求最小可行值”的标准模板这个模板建议直接记下来while (left right) { long mid left (right - left) / 2; if (check(mid)) { right mid; } else { left mid 1; } }当check(mid)返回true说明limit取mid已经可行答案不可能大于mid所以把右边界收缩到mid如果不可行说明mid太小答案必须大于mid所以左边界收缩到mid1。最后left和right重合那个值就是答案。这里写成left (right - left) / 2而不是(left right) / 2是为了防止两个巨大的long相加时溢出虽然这个题大概率不会爆但这是好习惯。canSplit函数的参数limit表示“每个批次的重量上限”函数内部用贪心统计最少需要多少个批次。segments从1开始因为至少有一个批次。遍历每个包裹时如果当前批次累加超重就开启新批次并把当前包裹放进新批次。注意这里current直接赋值为weight而不是先把current清零再加weight。如果segments已经超过k直接返回false不用继续遍历可以省掉很多无意义计算。为什么segments从1开始而不是0因为我们的切分逻辑是“先往当前批次里装装不下再开新批次”所以第一个包裹一定属于第一个批次批次数量在第1个包裹进第一个批次时就已经是1了。如果从0开始最后统计出来的批次数量会比真实值少1二分就会偏掉。4. 复杂度、边界与同类题扩展4.1 时间与空间复杂度这道题的时间复杂度是O(N log S)N是包裹数量S是数组总和。每次check函数完整遍历一遍数组需要O(N)二分区间长度近似S二分大约需要O(log S)次判断所以整体就是O(N log S)。假设N1e5S1e9二分次数大概在30次左右总操作量约300万对Java来说完全不是问题哪怕考试机器性能一般也能轻松跑过。空间复杂度是O(N)因为要存下整个数组w。如果你愿意可以在读入的时候同时算sum和max之后check函数再遍历数组这种实现已经是我上文代码的方式。还有更省空间的做法是在读入时就把数组存到ArrayList里或者用BufferedReader读大输入但对这道题的数据规模来说Scanner已经足够了。4.2 边界条件与数据范围边界情况是机考考察的重灾区LeetCode式的隐藏用例往往就藏在边界里。第一种情况是n1也就是只有一件包裹。此时数组最大值等于总和leftright二分循环根本不会进入直接输出这个包裹重量正确。第二种情况是k n也就是批次数不少于包裹数那每个包裹都可以单独作为一批答案就是max(w)同样由二分的起始范围天然保证。第三种情况是包裹重量有零有整甚至有0出现不用慌left可以从0开始也可以从最大值开始当最大值为0时答案就是0逻辑依旧成立。还要注意一个很多人忽略的点check函数中current weight这句虽然我们用的是long但weight是intJava会自动提升为long运算所以不会溢出。如果写的时候把current声明成int那就不行了。数据范围如果很大甚至可以考虑用BigInteger但一般没必要。4.3 这类题的通用套路“最小化最大子段和”属于典型的“二分答案贪心验证”问题。华为OD机考里这一类题目出现频率非常高只是外壳经常换。比如“在一条直线上放置广告牌相邻广告牌之间最小距离最大化”“把一堆木材切成若干段每段长度至少为多少最多能切多少段”“传送带上要完成一批任务总操作时间不能超过多少每小时最少处理多少件”这些看起来完全不同的题骨子里都是同一个套路。遇到这种题我一般会先问自己三个问题第一题目要求的最值是什么是“最小化最大值”还是“最大化最小值”第二如果给定一个候选值能不能用一次遍历判断它是否可行第三这个可行性判断的结果是否随着候选值单调变化三个问题如果都是肯定的就大胆地写二分答案。判断部分往往都能用贪心解决而贪心的正确性理由通常就是“尽早满足约束把不确定性留给后续”。这个套路还有一个变体如果题目不是求一个整数的limit而是求一个“切分的数量”比如“最多能切成多少段使得每段和不超过limit”那你只需要把canSplit函数稍加改造不再比较segments和k而是直接返回segments的值。面试和机考里经常会在同一个场景下换个问法核心算法其实没变。5. 机考实战经验双机位调试与做题节奏5.1 双机位摆放与调试细节我见过不少同学在机考前不看考试须知直接进入考场才发现第二机位没绑定好折腾了十几分钟才开始答题。华为OD机考的双机位调试建议提前一天到两天做一次完整的演练。首先把手机支架摆在桌子的侧后方高度大约和你的视线齐平或者略高一点镜头向下倾斜45度左右。自测的时候调整好角度之后先坐在椅子上正常敲键盘让朋友或者家人看画面里能不能完整看到你的双手和屏幕。如果你发现自己打字的姿势很靠前手肘超出了画面那就把手机往后挪一挪。如果屏幕反光很厉害稍微调整支架方向避免画面里一块白斑。然后是权限调试。手机端“考生端”App或小程序一般会申请摄像头和麦克风权限要给足。电脑端浏览器也要允许摄像头、麦克风权限进入考试页之前可以先在系统设置里试一下摄像头预览。我习惯在正式考试前开一个视频会议软件建一个只有自己的会议室看一眼画面和声音是不是正常这个办法非常简单粗暴但有效。还有一个小细节如果考试时间比较长手机录像是持续进行的耗电很快务必插上充电线。手机的内存如果太满可以提前清一点存储空间免得录像到一半写不进文件。5.2 做题顺序与时间分配华为OD机考常见的形式是三道题分值分布一般是100分、100分、200分时间通常两小时到两个半小时。我的经验是拿到试卷后先花两分钟到三分钟快速浏览三道题题干和数据范围给它们标一个难度排序。第一道题往往是字符串处理或者数组模拟这种题应该尽量在10到15分钟内AC拿到保底分数。第二道题和第三道题里如果出现了“快递投放”这种带明显算法模型的题比如看到“最小化最大值”“最多能分成多少段”这种关键词直接往二分答案方向想按上面给的模板写。整个编码加自测控制在30分钟左右是比较理想的状态。最难的那道题不要一上来就死磕先做能拿分的题最后留足时间想难题。还有一点很重要把每个样例都跑一遍再提交。OD机考的评测系统一般是按通过用例百分比给分不是非对即错所以哪怕你只写出了暴力解法只要时间复杂度能撑过部分小数据用例也能拿到一部分分数。千万不要因为“觉得自己的解法不是最优”就不提交先拿分再优化。5.3 现场突发的几个事故怎么处理机考现场多少会出点状况心态稳住是最重要的。网络闪断是最常见的事故。答题平台一般会自动保存已提交的代码和输入的数据重新连上网络之后刷新页面看看代码是否还在通常都在。不要自己关浏览器重开那样反而可能丢失状态。如果断网持续很久联系监考或者技术支持说明情况。手机画面中断也是一个高频问题。第二机位一旦黑屏监考系统会标记异常。这时候不要慌如果手机只是熄屏了点亮屏幕重新进入考生端如果App闪退重新扫码绑定。动作尽量慢一点让画面里的行为显得从容避免被误判为在做小动作。我一次考试时手机真的自动重启过全程大约一分钟后来成绩也没受影响所以这类偶发问题一般有容错机制但前提是你别频繁出状况。编译报错也要冷静处理。最常见的问题是类名不是Main、忘记import java.util.Scanner、代码里有中文标点。编译错误会直接显示按提示改掉再提交。如果你发现自己连编译都不能通过大概率是这些低级问题一句一行地排查就行。6. 常见问题速查与避坑记录6.1 代码相关的坑我把这道“快递投放问题”以及同类二分题里容易踩的坑整理成一张速查表平时记不清的时候翻一下很有用。问题现象可能原因解决办法编译不通过类名不叫Main或漏掉import语句类名改成Main打开import java.util.Scanner运行结果全是错误输入读取不对比如读错行确认第一行是n和k第二行是数组二分死循环left和right更新条件写反check为true时rightmid否则leftmid1答案偏小二分范围下界设置过低left从max(w)开始而不是从0答案偏大贪心判断段数时初始值写错segments从1开始因为至少有一个批次大数据case超时或者WAint溢出sum、left、right、mid、current全部使用long边界用例出错n1或kn没考虑确认二分起始范围已经正确覆盖边界情况6.2 考试环境相关的坑除了代码本身机考环境也容易出问题。第二机位手机中途熄屏多半是没关自动锁屏或者没有插电源。后台弹窗跳出来多半是没考前退出微信、QQ这类软件。房间里突然有人说话多半是没提前跟家人沟通好考试时间段。这些问题不是算法问题但一旦发生会严重影响考试状态。有一个很容易被忽略的点如果你电脑外接了显示器机考时最好把外接显示器拔掉。有些考场监控系统会检测到多块屏幕直接判定为高风险行为。这个细节很多同学觉得无所谓但其实很敏感没必要的设备就别开。还有桌面上不要放任何纸质资料包括面试笔记、面经文档打印件。就算你全程不碰摄像头画面里出现了也会被误判。6.3 我的几点真实体会准备这类二分答案题我个人的经验是不要急着写代码先把“单调性在哪里”找出来。判断可行性是贪心还是DP也提前想明白。像“快递投放”这道题check函数一旦写好整体代码不会超过50行真正值钱的是能不能在考场上快速识别出“这是个二分答案问题”。最后分享一个我自己用着很顺手的小技巧把check函数单独拎出来命名成canSplit或者feasible这种带判断含义的名字主流程只保留输入、初始化和二分。这样代码结构清晰出bug也好定位。很多同学习惯把所有逻辑堆在main里一旦二分边界出错调试起来非常痛苦。其实这类“包裹投放”“任务分配”的题目多做几道之后会形成肌肉记忆。刷题时除了看标准题解建议自己动手把二分模板默写几遍包括long的使用、segments的初始值、mid的更新方式这些细节默写到不需要思考考试时才能把精力留给真正想不通的地方。
华为OD机考C卷“快递投放”题解：二分答案与Java实现
准备考华为OD机考的同学对“双机位C卷”这几个字应该都不会陌生。机考系统会要求你提前架好正面摄像头和第二机位手机从侧后方45度对准桌面和屏幕全程录像。我第一次考的时候光调摄像头角度就折腾了快二十分钟手忙脚乱。但说句实话比起设备调试真正决定能不能通过的是算法题。今天想聊的这道“快递投放问题”是C卷里比较有代表性的一道中等题用Java实现起来不算复杂但思路如果没梳理清楚很容易在二分边界上卡住。文章会从考试环境讲起再完整拆解题目、给出可直接运行的Java代码最后补上一波机考实战经验和踩坑记录适合正在准备华为OD机考、或者想研究OD机试题型和面经的同学参考。1. 华为OD机考与双机位先搞清楚考试环境1.1 双机位到底怎么回事华为OD机考对着装和操作环境有一定要求最直观的就是双机位监控。所谓“双机位”通常指两个摄像设备同时参与监控正面一个摄像头对着你本人侧面一个摄像头对着你的双手、键盘和屏幕。正面机位一般用笔记本电脑自带摄像头或者外接USB摄像头就能解决侧面机位一般要求使用手机或平板通过指定的“考生端”App或小程序扫码绑定后把画面实时回传。这里面有个很关键的细节第二机位的摆放不是随便拿手机支在桌上就行。考官要求侧后方45度左右、距离半米到一米五之间能同时拍到你的上半身、手部动作和完整的电脑屏幕。角度太正容易挡住屏幕反光角度太偏画面里只能看到你的侧脸不符合要求。稳妥的做法是先把手机架好打开摄像头预览自己在座位上模拟敲代码的姿势确认画面里双手、键盘、屏幕都在取景范围内再进入正式考试。手机支架我建议提前买一个能夹桌边的那种比用书本垫稳得多考试中途低头调手机会非常被动。还要注意手机在考试期间不能熄屏不少同学忘记关闭自动锁屏或者被来电打断导致第二机位画面中断。比较成熟的方案是考前把手机调到“勿扰模式”或“飞行模式WiFi”然后插上充电线。飞行模式能挡掉来电和通知WiFi保证网络和录像上传不受影响充电线保证几个小时不掉电。这个操作很普通但能避免掉很多考中出现的小事故。1.2 环境检查清单考前必做机考环境以“干净、安静、无遮挡”为标准。我整理了一份自己考前会过一遍的清单虽然不是官方的正式文件但按这个思路准备基本上能应对多数考场的要求。房间方面选光线充足且没有逆光的书桌背后不要有大窗户或强光源否则人脸在画面里是黑的。桌面只留电脑、鼠标、键盘和水杯其他东西全部收走。有些批次明确禁止草稿纸和笔有些允许具体以邮件或考试系统通知为准不确定的情况下我建议不准备直接在电脑上做临时备注。房间门可以关上提前和同住的人打好招呼考试时间段不要进房间避免有人声或者走动被判定为异常。电脑方面考试前关闭所有不必要的软件弹窗微信、QQ、Outlook这类即时通讯工具最好直接退出。有人习惯开着浏览器查代码考前也全部清掉只保留考试系统页面。摄像头和麦克风权限要提前授权有些浏览器会拦截进入考试页之后才弹权限确认框就会白白浪费几分钟。网络方面尽量用有线网或者稳定的WiFi如果网络闪断做题界面会有影响后面我会专门讲抢救办法。2. “快递投放”题目拆解这道题到底在考什么2.1 题目描述与数据模型“快递投放”这个题名在不同批次的C卷里表述可能不完全一样有的是“包裹分拣”有的是“货物运输”但剥掉外壳之后的核心模型是一致的。我以最常见的描述给你还原一遍自动化分拣线上有N件包裹按顺序经过投递口每件包裹的重量为w[i]。分拣员需要把相邻的若干件包裹打包成一个“投放批次”每个批次的总重量不能超过投放车的承重上限limit。现在公司最多允许安排K个批次完成所有包裹的投放问承载上限limit至少设置为多少才能保证用不超过K个批次装完所有包裹换一种更技术的说法给定数组w最多分成K个连续子数组求所有子数组和的最大值中最小的那个是多少。这就是经典的“最小化最大子段和”问题LeetCode 410就是同款。输入输出格式一般是这样的输入 5 2 7 2 5 10 8 输出 18数组[7,2,5,10,8]K2最优切法是把[7,2,5]放在一个批次[10,8]放在另一个批次两个批次重量分别是14和18答案就是18。如果用别的方式切比如[7,2,5,10]和[8]最大段是24不如18。2.2 先避开一个常见误区很多同学拿到题的第一反应是“总共K段那把总和除以K得到平均值每段尽量往平均值上凑不就行了”。这个思路大方向没有错但包裹顺序是固定的单个包裹又不能拆开你没法让每一段都精确落在平均值附近。如果你直接随便定一个上限从左到右去切切出来的段数可能超过K也可能已经能装下却提前切了导致最大段变大。上限定多少本身就需要搜索。举个例子w[3,2,5,4]K2。总和是14平均值是7。如果以7作为上限从左到右切325549超过7所以段1是[3,2]段2是[5]不对547段2只能单独[5]段3是[4]一共3段超过了K。那把上限提到8呢32510超过8还是切[3,2]、[5]、[4]仍然是3段。再把上限提到932510超过9段1是[3,2]段2是[5,4]正好2段最大段和是9。所以答案其实是9而不是平均值7。这一步就很关键上限7和8都不行9才可行最优值需要在一定范围内逐个尝试或者聪明地搜索。2.3 二分答案的推导过程既然“上限定多少”需要搜索那能不能高效搜索能。注意一个性质当上限limit增大时在“每段重量不超过limit”的前提下最少需要的段数一定不会变多。因为上限越大每个批次能装的东西越多自然可以用更少的批次。反过来上限越小段数一定越多。这个性质叫单调性有了单调性就可以用二分答案。具体思路是这样的先确定答案落在哪个区间里。下限是数组中的最大值max(w)因为重达max的那件包裹无论怎么切至少需要一个批次单独承载它上限是数组总和sum(w)因为把所有包裹放进一个批次也满足约束。然后在这个区间里二分查找第一个“可行”的值也就是使所需段数不超过K的最小limit。判断某个limit是否可行用贪心从左到右切当前批次累积重量cur遇到下一个包裹w如果curw仍然不超过limit就继续放进当前批次如果超过就新开一个批次让当前包裹作为新批次的第一个。这种“能装就装装不下才换”的切法是给定上限时能得到最少段数的切法因为切得越晚前面的批次装得越满留给后面的包裹就越少段数不可能更多。这个贪心是安全的。我用上面那个[3,2,5,4]K2的例字走一遍二分流程left5right14。mid9check发现最少2段可行于是right9尝试更小的值。new left5,right9,mid7check发现最少3段不可行于是left8。new left8,right9,mid8check发现最少3段不可行于是left9。leftright9输出答案9。整个思考链条是这样的先看懂题面要求什么发现是“限制一个上限判断段数是否够用”再发现“段数随上限单调变化”最后决定二分去查找最小可行值。这就是二分答案的标准套路。3. Java实现直接能跑的完整代码3.1 OD机考的Java输入输出模板华为OD机考使用Java提交时一般要求写一个Main类从标准输入读取数据把结果打印到标准输出。这个和平时刷LeetCode只需要填函数体不太一样很多同学第一次上机就挂在输入输出上。读取部分直接用Scanner就够了。第一行通常是两个整数n和k第二行是n个整数。Scanner的nextInt方法会跳过空格和换行所以不管是单行还是多行输入都能处理。输出部分用System.out.println题目要求输出一个整数就只输出这个整数不要画蛇添足打印别的提示信息。类名一定要是Main如果你写成Test或者别的名字云端编译会直接报错。3.2 完整代码下面是这道“快递投放问题”的完整Java实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); int[] w new int[n]; long sum 0; int max 0; for (int i 0; i n; i) { w[i] sc.nextInt(); sum w[i]; if (w[i] max) { max w[i]; } } long left max; long right sum; while (left right) { long mid left (right - left) / 2; if (canSplit(w, k, mid)) { right mid; } else { left mid 1; } } System.out.println(left); sc.close(); } private static boolean canSplit(int[] w, int k, long limit) { int segments 1; long current 0; for (int weight : w) { if (current weight limit) { segments; current weight; if (segments k) { return false; } } else { current weight; } } return true; } }这段代码唯一需要注意的地方是sum、left、right、mid、current这些变量都用了long而不是int。因为数组长度和数据范围大的时候总和可能超过int上限int会溢出变成负数二分直接乱掉。这是华为OD机考里非常容易踩的一个雷。3.3 关键代码逐段讲解二分部分用的是“求最小可行值”的标准模板这个模板建议直接记下来while (left right) { long mid left (right - left) / 2; if (check(mid)) { right mid; } else { left mid 1; } }当check(mid)返回true说明limit取mid已经可行答案不可能大于mid所以把右边界收缩到mid如果不可行说明mid太小答案必须大于mid所以左边界收缩到mid1。最后left和right重合那个值就是答案。这里写成left (right - left) / 2而不是(left right) / 2是为了防止两个巨大的long相加时溢出虽然这个题大概率不会爆但这是好习惯。canSplit函数的参数limit表示“每个批次的重量上限”函数内部用贪心统计最少需要多少个批次。segments从1开始因为至少有一个批次。遍历每个包裹时如果当前批次累加超重就开启新批次并把当前包裹放进新批次。注意这里current直接赋值为weight而不是先把current清零再加weight。如果segments已经超过k直接返回false不用继续遍历可以省掉很多无意义计算。为什么segments从1开始而不是0因为我们的切分逻辑是“先往当前批次里装装不下再开新批次”所以第一个包裹一定属于第一个批次批次数量在第1个包裹进第一个批次时就已经是1了。如果从0开始最后统计出来的批次数量会比真实值少1二分就会偏掉。4. 复杂度、边界与同类题扩展4.1 时间与空间复杂度这道题的时间复杂度是O(N log S)N是包裹数量S是数组总和。每次check函数完整遍历一遍数组需要O(N)二分区间长度近似S二分大约需要O(log S)次判断所以整体就是O(N log S)。假设N1e5S1e9二分次数大概在30次左右总操作量约300万对Java来说完全不是问题哪怕考试机器性能一般也能轻松跑过。空间复杂度是O(N)因为要存下整个数组w。如果你愿意可以在读入的时候同时算sum和max之后check函数再遍历数组这种实现已经是我上文代码的方式。还有更省空间的做法是在读入时就把数组存到ArrayList里或者用BufferedReader读大输入但对这道题的数据规模来说Scanner已经足够了。4.2 边界条件与数据范围边界情况是机考考察的重灾区LeetCode式的隐藏用例往往就藏在边界里。第一种情况是n1也就是只有一件包裹。此时数组最大值等于总和leftright二分循环根本不会进入直接输出这个包裹重量正确。第二种情况是k n也就是批次数不少于包裹数那每个包裹都可以单独作为一批答案就是max(w)同样由二分的起始范围天然保证。第三种情况是包裹重量有零有整甚至有0出现不用慌left可以从0开始也可以从最大值开始当最大值为0时答案就是0逻辑依旧成立。还要注意一个很多人忽略的点check函数中current weight这句虽然我们用的是long但weight是intJava会自动提升为long运算所以不会溢出。如果写的时候把current声明成int那就不行了。数据范围如果很大甚至可以考虑用BigInteger但一般没必要。4.3 这类题的通用套路“最小化最大子段和”属于典型的“二分答案贪心验证”问题。华为OD机考里这一类题目出现频率非常高只是外壳经常换。比如“在一条直线上放置广告牌相邻广告牌之间最小距离最大化”“把一堆木材切成若干段每段长度至少为多少最多能切多少段”“传送带上要完成一批任务总操作时间不能超过多少每小时最少处理多少件”这些看起来完全不同的题骨子里都是同一个套路。遇到这种题我一般会先问自己三个问题第一题目要求的最值是什么是“最小化最大值”还是“最大化最小值”第二如果给定一个候选值能不能用一次遍历判断它是否可行第三这个可行性判断的结果是否随着候选值单调变化三个问题如果都是肯定的就大胆地写二分答案。判断部分往往都能用贪心解决而贪心的正确性理由通常就是“尽早满足约束把不确定性留给后续”。这个套路还有一个变体如果题目不是求一个整数的limit而是求一个“切分的数量”比如“最多能切成多少段使得每段和不超过limit”那你只需要把canSplit函数稍加改造不再比较segments和k而是直接返回segments的值。面试和机考里经常会在同一个场景下换个问法核心算法其实没变。5. 机考实战经验双机位调试与做题节奏5.1 双机位摆放与调试细节我见过不少同学在机考前不看考试须知直接进入考场才发现第二机位没绑定好折腾了十几分钟才开始答题。华为OD机考的双机位调试建议提前一天到两天做一次完整的演练。首先把手机支架摆在桌子的侧后方高度大约和你的视线齐平或者略高一点镜头向下倾斜45度左右。自测的时候调整好角度之后先坐在椅子上正常敲键盘让朋友或者家人看画面里能不能完整看到你的双手和屏幕。如果你发现自己打字的姿势很靠前手肘超出了画面那就把手机往后挪一挪。如果屏幕反光很厉害稍微调整支架方向避免画面里一块白斑。然后是权限调试。手机端“考生端”App或小程序一般会申请摄像头和麦克风权限要给足。电脑端浏览器也要允许摄像头、麦克风权限进入考试页之前可以先在系统设置里试一下摄像头预览。我习惯在正式考试前开一个视频会议软件建一个只有自己的会议室看一眼画面和声音是不是正常这个办法非常简单粗暴但有效。还有一个小细节如果考试时间比较长手机录像是持续进行的耗电很快务必插上充电线。手机的内存如果太满可以提前清一点存储空间免得录像到一半写不进文件。5.2 做题顺序与时间分配华为OD机考常见的形式是三道题分值分布一般是100分、100分、200分时间通常两小时到两个半小时。我的经验是拿到试卷后先花两分钟到三分钟快速浏览三道题题干和数据范围给它们标一个难度排序。第一道题往往是字符串处理或者数组模拟这种题应该尽量在10到15分钟内AC拿到保底分数。第二道题和第三道题里如果出现了“快递投放”这种带明显算法模型的题比如看到“最小化最大值”“最多能分成多少段”这种关键词直接往二分答案方向想按上面给的模板写。整个编码加自测控制在30分钟左右是比较理想的状态。最难的那道题不要一上来就死磕先做能拿分的题最后留足时间想难题。还有一点很重要把每个样例都跑一遍再提交。OD机考的评测系统一般是按通过用例百分比给分不是非对即错所以哪怕你只写出了暴力解法只要时间复杂度能撑过部分小数据用例也能拿到一部分分数。千万不要因为“觉得自己的解法不是最优”就不提交先拿分再优化。5.3 现场突发的几个事故怎么处理机考现场多少会出点状况心态稳住是最重要的。网络闪断是最常见的事故。答题平台一般会自动保存已提交的代码和输入的数据重新连上网络之后刷新页面看看代码是否还在通常都在。不要自己关浏览器重开那样反而可能丢失状态。如果断网持续很久联系监考或者技术支持说明情况。手机画面中断也是一个高频问题。第二机位一旦黑屏监考系统会标记异常。这时候不要慌如果手机只是熄屏了点亮屏幕重新进入考生端如果App闪退重新扫码绑定。动作尽量慢一点让画面里的行为显得从容避免被误判为在做小动作。我一次考试时手机真的自动重启过全程大约一分钟后来成绩也没受影响所以这类偶发问题一般有容错机制但前提是你别频繁出状况。编译报错也要冷静处理。最常见的问题是类名不是Main、忘记import java.util.Scanner、代码里有中文标点。编译错误会直接显示按提示改掉再提交。如果你发现自己连编译都不能通过大概率是这些低级问题一句一行地排查就行。6. 常见问题速查与避坑记录6.1 代码相关的坑我把这道“快递投放问题”以及同类二分题里容易踩的坑整理成一张速查表平时记不清的时候翻一下很有用。问题现象可能原因解决办法编译不通过类名不叫Main或漏掉import语句类名改成Main打开import java.util.Scanner运行结果全是错误输入读取不对比如读错行确认第一行是n和k第二行是数组二分死循环left和right更新条件写反check为true时rightmid否则leftmid1答案偏小二分范围下界设置过低left从max(w)开始而不是从0答案偏大贪心判断段数时初始值写错segments从1开始因为至少有一个批次大数据case超时或者WAint溢出sum、left、right、mid、current全部使用long边界用例出错n1或kn没考虑确认二分起始范围已经正确覆盖边界情况6.2 考试环境相关的坑除了代码本身机考环境也容易出问题。第二机位手机中途熄屏多半是没关自动锁屏或者没有插电源。后台弹窗跳出来多半是没考前退出微信、QQ这类软件。房间里突然有人说话多半是没提前跟家人沟通好考试时间段。这些问题不是算法问题但一旦发生会严重影响考试状态。有一个很容易被忽略的点如果你电脑外接了显示器机考时最好把外接显示器拔掉。有些考场监控系统会检测到多块屏幕直接判定为高风险行为。这个细节很多同学觉得无所谓但其实很敏感没必要的设备就别开。还有桌面上不要放任何纸质资料包括面试笔记、面经文档打印件。就算你全程不碰摄像头画面里出现了也会被误判。6.3 我的几点真实体会准备这类二分答案题我个人的经验是不要急着写代码先把“单调性在哪里”找出来。判断可行性是贪心还是DP也提前想明白。像“快递投放”这道题check函数一旦写好整体代码不会超过50行真正值钱的是能不能在考场上快速识别出“这是个二分答案问题”。最后分享一个我自己用着很顺手的小技巧把check函数单独拎出来命名成canSplit或者feasible这种带判断含义的名字主流程只保留输入、初始化和二分。这样代码结构清晰出bug也好定位。很多同学习惯把所有逻辑堆在main里一旦二分边界出错调试起来非常痛苦。其实这类“包裹投放”“任务分配”的题目多做几道之后会形成肌肉记忆。刷题时除了看标准题解建议自己动手把二分模板默写几遍包括long的使用、segments的初始值、mid的更新方式这些细节默写到不需要思考考试时才能把精力留给真正想不通的地方。
