一、题目描述
火车站附近的货物中转站负责将到站货物运往仓库，小明在中转站负责调度 2K 辆中转车(K辆干货中转车，K 辆湿货中转车)货物由不同供货商从各地发来，各地的货物是依次进站，然后小明按照卸货顺序依次装货到中转车，一个供货商的货只能装到一辆车上不能拆装，但
是一辆车可以装多家供货商的货：中转车的限载货物量由小明统一指定，在完成货物中转的前提下，请问中转车的统一限载货物数最小值为多少。
二、输入描述
第一行 length 表示供货商数量 1 <= length <= 10；
第二行 goods 表示供货数数组 1 <= goods[i] <= 10；
第三行 types[i]表示对应货物类型，types[i]等于 0 或者 1，其中 0 代表干货，1 代表湿货；
第四行 k 表示单类中转车数量 1 <= k <= goods.length；
三、输出描述
运行结果输出一个整数，表示中转车统一限载货物数。
备注：中转车最多跑一趟仓库。
四、题目解析
货物由不同供货商从各地发来，各地的货物是依次进站，然后小明按照卸货顺序依次装货到中转车，一个供货商的货只能装到一辆车上，不能拆装，但是一辆车可以装多家供货商的货；这意味着，我们不难改变输入的顺序，要按照输入的顺序去装车。并且干货只能装到干货车，
湿货只能装到湿货车。
比如用例 1 中:
4
3 2 6 3
0 1 1 0
2
第 1 个货物是: 干货，因此装到干货车
第 2 个货物是:湿货，由于湿货不难装到干货车，因此第一辆车只装一个货物就必须走。第二个货物需要装到一辆湿货车上。
第 3 个货物是:湿货，前一步的湿货车还没走，此时我们有两种选择。将第 3 个货物继续装到前面的湿货车上，即和第 2 个货物装一起，但是会导致最低限载被提高。将第 3 个货物装到下一辆湿货车上。
第 4 个货物是:干货，因此只能重新要一辆干货车，继续装载说到这里，大家可能已经感觉出来，连续的 0(干货)可以用一辆车运，也可以分成多辆车运，而一旦连续 0(干货)被中断，即出现了 1(湿货)，则前面的干货车必须走，这个湿货需要申请一辆湿货车来运根据上面逻辑，我们可以将连续干货 和 连续湿货 对应的区间段统计出来:
连续干货：[3]、[3]
连续湿货：[2,6]
- 如果连续干货的区间段数 刚好等于 k，则刚好每段连续干货，都可以分配一辆干货车；
- 如果连续干货的区间段数<k，则出了必要的给每段分配一辆干货车外，还有多余的干货车可以继续分配:此时，我们应该将多段连续干货，按照和大小降序，优先给 和最大 的连续干货段多分配一辆车，即相当于将一个区间一分为二，这样最低限载就降低了，并且多出的干货车数量减 1。如果多余的干货车数量不等于 0，则继续按上面逻辑，分配一辆车给 和最大 的连续干货段。直到多余的干货车用完。
- 如果连续干货的区间段数 >k，此时是无法完成运输任务的，应该视为异常情况，但是本题没有说明异常处理，因此可以认为此场景不存在。
上面逻辑中，每次将区间一份为二后，都要重新按照 区间和大小降序，这里可以用 优先队列。
五、解题思路
- 读取输入的供货商数量 length，供货数数组 goods，货物类型数组 types，单类中转车数量 k；
- 创建两个优先队列 drys 和 wets，用于存储干货和湿货的信息；优先队列按照货物数量从大到小进行排序；
- 使用变量 isDry 标记当前处理的货物类型是否为干货，初始值为 true；
- 创建一个临时链表 tmp 和变量 sum，用于记录当前处理的一类货物的数量总和；
- 遍历供货商的数量，根据货物类型判断是否为干货，如果是干货，则将其数量添加到临时链表 tmp 中，并更新总和 sum；如果是湿货，则判断当前处理的货物类型，如果是干货，则将临时链表 tmp 添加到 drys 中，并重新初始化临时链表和总和，然后将湿货的数量添加到临时链表 tmp 中，并更新总和 sum，并更新当前处理的货物类型为湿货；
- 遍历结束后，将剩余的临时链表 tmp 添加到对应的优先队列中；
- 调用 divide 方法对干货和湿货的优先队列进行划分，保证每辆中转车的货物数最小；
- 返回干货和湿货中划分后的最大值作为中转车的统一限载货物数；
六、Python算法源码
import heapq
def get_result(n, goods, types, k):
# 初始化干物和湿物数组、临时数组、重量、是否为干物
drys = []
wets = []
isDry = True
tmp = []
s = 0
# 遍历货物列表
for i in range(n):
# 如果当前货物为干物
if types[i] == 0:
# 如果之前已经遇到湿物，则将当前临时数组中的湿物进行分割并添加到湿物数组中
if not isDry:
tmp.insert(0, s)
# 将临时数组压入堆中，以便后续处理
heapq.heappush(wets, [-tmp[0], tmp])
# 清空临时数组和重量，并设置为干物
tmp = []
s = 0
isDry = True
# 将当前干物添加到临时数组中，并累加重量
tmp.append(goods[i])
s += goods[i]
# 如果当前货物为湿物
else:
# 如果之前已经遇到干物，则将当前临时数组中的干物进行分割并添加到干物数组中
if isDry:
tmp.insert(0, s)
# 将临时数组压入堆中，以便后续处理
heapq.heappush(drys, [-tmp[0], tmp])
# 清空临时数组和重量，并设置为湿物
tmp = []
s = 0
isDry = False
# 将当前湿物添加到临时数组中，并累加重量
tmp.append(goods[i])
s += goods[i]
# 处理最后一个临时数组，将其压入相应的堆中
tmp.insert(0, s)
if isDry:
heapq.heappush(drys, [-tmp[0], tmp])
else:
heapq.heappush(wets, [-tmp[0], tmp])
# 对干物和湿物数组进行分割操作，求出最小值
dry_min = divide(drys, k)
wet_min = divide(wets, k)
# 返回干物和湿物两个最小值的较大者
return max(dry_min, wet_min)
# 分割函数，用于将货物列表分割成k个子列表，使得每个子列表的总重量最小
def divide(goods, k):
# 当货物列表长度小于k时，需要将其分割成k个子列表
while len(goods) < k:
# 取出当前堆中重量最大的元素（也就是第一个元素），并获取其对应的货物列表
top = heapq.heappop(goods)[1]
# 如果货物列表为空，则退出循环
if not top: break
# 获取干物的重量
dry_sum = top.pop(0)
# 如果该货物列表只有一个元素，则直接返回其重量
if len(top) == 1:
return dry_sum
# 初始化分割点、分割后的长度、当前长度和干物重量
splitIdx = 0
splitHalf = 0
half = 0
mn = dry_sum
# 遍历货物列表，寻找最小的分割点，使得分割后的两个子列表中总重量的最大值最小
for i in range(1, len(top)):
val = top[i - 1]
half += val
mx = max(half, dry_sum - half)
if mx < mn:
mn = mx
splitIdx = i
splitHalf = half
# 将货物列表分割成两个子列表，并将其压入堆中
halfList = [splitHalf] + top[:splitIdx]
heapq.heappush(goods, [-halfList[0], halfList])
otherHalfList = [dry_sum - splitHalf] + top[splitIdx:]
heapq.heappush(goods, [-otherHalfList[0], otherHalfList])
# 最终返回货物列表中第一个元素的重量，即为分割后子列表中总重量的最小值
return goods[0][1][0]
七、效果展示
1、输入
4
3 2 6 3
0 1 1 0
2
2、输出
6
🏆下一篇：华为OD机试真题 Python 实现【相对开音节】【2022Q4 100分】，附详细解题思路
🏆本文收录于，华为OD机试（Python）真题（A卷+B卷）
每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。