一、题目描述
火车站附近的货物中转站负责将到站货物运往仓库,小明在中转站负责调度 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在线答疑。