题意:将按 ID 递增排列的 N 个旅行团(人数为数组 P[1..N])切分成 M 个连续段(每段对应一节车厢),每个旅行团整体必须在同一车厢。目标是让各车厢人数的最大值记为 X、最小值记为 Y,使 X - Y 最小,要求输出对应方案中的 X。
关键结论(直观且常用于竞赛):
要让差异 X - Y 尽量小,首先必须把最大车厢人数 X 压到尽可能小。
一旦存在某个划分的最大值高于可实现的“最小可能最大段和”,我们就能找到一个最大值更小的划分,从而不会使差异变得更好。因此,最终输出的 X 等于把数组切成 M 段时的最小可能最大段和。这正是经典问题 “分割数组的最大值最小化(Split Array Largest Sum)”。
实现方法(算法组合:二分答案 + 贪心检查):
某旅行线路上有一辆有 M 节车厢的列车,所有车厢中都没人,现有 N 个旅行团需要搭乘该线路,其 ID 为 :[0,N) 。请给出具体的乘坐方案,满足使得各车厢间的乘客数量差异最小。(说明:乘客最多的车厢中的人数记作 X ,乘客最少的车厢中的人数记作 Y ,需要满足 X−Y 最小) 旅行团乘坐列车需要满足如下要求:
1.对于任意 0<i<j<M ,车厢i中的任意旅行团的 ID 小于车厢 j 中任意旅行团的 ID 。
2.同个车厢内的旅行团,他们的 ID 是连续的。
3.同个旅行团的成员必须在一个车厢内。
注:当只有一个车厢时,该车厢的乘客数既是最大乘客数,也是最小乘客数
第 1 行:N M,其中
N 是旅行团个数,范围是 [1,1000]
M 是车厢个数,范围是 [1,N]
第 2 行:P1 P2 ... PN ,每个数字代表一个旅行团的成员个数,成员个数范围是 [1,100000]
输出乘客最多的车厢中的人数 X
输入
3 3
1 6 4
输出
6
说明
3 3 :有 3 个旅行团,列车有 3 节车厢
1 6 4 :这 3 个旅行团的成员个数分别是 1 6 4
每个车厢都有旅行团时车厢人数差异才可能最小,考虑以下 1 种乘坐方案
可知乘客最多的车厢中的人数是 6
输入
5 2
7 2 5 10 8
输出
18
说明
5 2 :有 5 个旅行团,列车有 2 节车厢
7 2 5 10 8 :这 5 个旅行团的成员个数分别是 7 2 5 10 8
每个车厢都有旅行团时车厢人数差异才可能小,因此只考虑以下 4 种乘坐方案
[7][2 5 10 8] :7 和 25 ,人数差异 18
[7 2][5 10 8] :9 和 23 ,人数差异 14
[7 2 5][10 8] :14 和 18 ,人数差异 4
[7 2 5 10][8] :24 和 8 ,人数差异 16
可知最好的方式是 [7 2 5][10 8] ,其中乘客最多的车厢中的人数是 18