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