将一串不能调换顺序的练习分到若干组时,平均值只给出参考,未必存在刚好平均的切分。目标若是让最重的一组尽量轻,就要检查每个切分点,而不能随意把困难关卡挪到别处。
明确本例规则
本例难度为正整数,要求分成给定数量的非空连续组。先猜一个容量上限,从左到右尽量装入当前组,下一项放不下才开新组。若所需组数不超过目标,说明容量可行;对容量区间做二分,寻找最小可行值。
输入与逐步结果
顺序难度[12, 16, 6, 16, 18, 3, 12, 5, 12, 9],要求分为5组。
下界 | 上界 | 候选 | 贪心组数 | 可行 [18, 109, 63, 2, True] [18, 63, 40, 3, True] [18, 40, 29, 5, True] [18, 29, 23, 6, False] [24, 29, 26, 6, False] [27, 29, 28, 5, True] [27, 28, 27, 6, False] 最小容量28,切点(2, 4, 5, 7),各组总难度[28, 22, 18, 15, 26]。 容量再减一:需要6组,超过限制。
编号仅标识本次案例中的对象,不能把它当成重要性排名。复算时先保留原输入,再按表格顺序记录中间状态。零值、空列表和未到达各有含义,不能因为显示相似就合并处理。需要分数的地方保存精确值,小数只用于阅读。
结果如何核对
下界是单项最大难度,上界是全部难度之和。判定函数用不超过组数,是因为正数序列中的现有组还能继续拆开,直到恰好达到目标组数。二分表记录每次上下界、候选容量、所需组数和判断。
得到最小上限后仍需给出一份合法切分。本例在所有可行切分中按切点序列选最小者,方便复算。再检查比答案小一的容量不可行,能说明答案不是仅仅找到了某个足够宽松的上限。
使用边界
本例不允许空组、乱序或把一项拆成小段,也没有组间切换额外成本。若出现负难度,尽量装满的单调判定不再直接适用。这里优化的是最重组的和,不是各组方差或最短完成时间。
练习可以先保持其他条件不变,只调整一项输入,观察哪个中间步骤首先产生差异。如果结果不同,先确认单位、端点和同值处理是否一致,再查具体运算。最终答案应与输入和过程一起保存,才方便判断这份结论适用于什么情境。
