电厂煤炭仓储分配问题：如何实现O(nlogn)复杂度解法？

问题回顾 #

给定煤炭配送列表A和仓库容量T，每批煤炭必须存入单个仓库，优先选择编号最小且剩余容量足够的仓库。需找到最后一批煤炭存入的仓库编号。

核心思路 #

要优化O(n²)的遍历查找，我们需要一个能高效查询剩余容量≥当前煤炭吨数的最小编号仓库的数据结构。这里采用「分组+有序集合」的方案：

• 用字典将仓库按剩余容量分组，每个剩余容量对应一个按编号升序排列的仓库列表。
• 用有序集合维护所有非零的剩余容量值，方便快速找到≥当前吨数的最小剩余容量阈值。
• 用哈希表记录每个仓库的最新剩余容量，确保状态准确。

具体步骤 #

1. 初始化结构：

   • remaining_groups：字典，键为剩余容量，值为按编号升序的仓库列表。
   • capacity_set：有序集合，存储所有非零的剩余容量值。
   • warehouse_rem：哈希表，记录每个仓库的当前剩余容量。
   • max_id：当前已使用的最大仓库编号，初始为-1。

2. 遍历每批煤炭：
   对于当前煤炭吨数a：

   • 查找可用仓库：在capacity_set中找到第一个≥a的剩余容量值target_cap。
   • 使用已有仓库：若找到target_cap：
     1. 从remaining_groups[target_cap]中取出编号最小的仓库id。
     2. 计算新剩余容量new_rem = warehouse_rem[id] - a。
     3. 从remaining_groups[target_cap]中移除id，若列表为空则从capacity_set中删除target_cap。
     4. 更新warehouse_rem[id]为new_rem。
     5. 若new_rem > 0，将id加入remaining_groups[new_rem]，并将new_rem加入capacity_set（若不存在）。
     6. 若为最后一批，记录id为答案。
   • 新开仓库：若未找到target_cap：
     1. max_id += 1，新仓库编号为max_id。
     2. 计算新剩余容量new_rem = T - a。
     3. 更新warehouse_rem[max_id]为new_rem。
     4. 若new_rem > 0，将max_id加入remaining_groups[new_rem]，并将new_rem加入capacity_set（若不存在）。
     5. 若为最后一批，记录max_id为答案。

代码示例（Python） #

依赖sortedcontainers库实现有序集合和有序列表：

from sortedcontainers import SortedSet, SortedList

def find_last_warehouse(A, T):
    remaining_groups = dict()  # key: 剩余容量, value: SortedList[仓库编号]
    capacity_set = SortedSet()
    warehouse_rem = dict()
    max_id = -1
    answer = -1

    for idx, a in enumerate(A):
        # 查找第一个≥a的剩余容量
        pos = capacity_set.bisect_left(a)
        if pos < len(capacity_set):
            target_cap = capacity_set[pos]
            # 获取编号最小的仓库
            warehouse_id = remaining_groups[target_cap][0]
            # 更新剩余容量
            new_rem = warehouse_rem[warehouse_id] - a
            # 移除旧记录
            remaining_groups[target_cap].remove(warehouse_id)
            if not remaining_groups[target_cap]:
                del remaining_groups[target_cap]
                capacity_set.remove(target_cap)
            # 更新仓库剩余
            warehouse_rem[warehouse_id] = new_rem
            # 若还有剩余，加入分组
            if new_rem > 0:
                if new_rem not in remaining_groups:
                    remaining_groups[new_rem] = SortedList()
                    capacity_set.add(new_rem)
                remaining_groups[new_rem].add(warehouse_id)
            # 记录最后一批的仓库编号
            if idx == len(A)-1:
                answer = warehouse_id
        else:
            # 新开仓库
            max_id += 1
            new_rem = T - a
            warehouse_rem[max_id] = new_rem
            if new_rem > 0:
                if new_rem not in remaining_groups:
                    remaining_groups[new_rem] = SortedList()
                    capacity_set.add(new_rem)
                remaining_groups[new_rem].add(max_id)
            # 记录最后一批的仓库编号
            if idx == len(A)-1:
                answer = max_id
    return answer

# 示例测试
A = [1, 6, 2, 10, 8, 3, 1]
T = 10
print(find_last_warehouse(A, T))  # 输出: 0

复杂度分析 #

• 每个仓库的加入、移除操作均为O(logk)（k为对应集合的大小）。
• 每批煤炭的处理涉及O(logm)的有序集合查询（m为不同剩余容量的数量）。
• 总时间复杂度为O(nlogn)，空间复杂度为O(n)，符合题目要求。

无第三方库的替代实现思路 #

若无法使用sortedcontainers，可通过以下方式模拟：

• 用列表维护capacity_set，每次插入时用bisect.insort保持有序，查询时用bisect.bisect_left。
• 每个剩余容量对应的仓库列表用普通列表，每次插入时用bisect.insort保持有序。
• 这种方式的时间复杂度仍为O(nlogn)，因为每次插入和查询都是O(logn)级别的操作。

内容的提问来源于stack exchange，提问作者PK96