每日一题——Python实现PAT乙级1020 月饼（举一反三+思想解读+逐步优化）

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

我的写法

专业点评：

时间复杂度分析：

空间复杂度分析：

总结：

我要更强

时间复杂度优化：

空间复杂度优化：

优化后的代码解释：

时间复杂度分析：

空间复杂度分析：

总结：

哲学和编程思想

1. 贪心算法（Greedy Algorithm）

2. 优先队列（Priority Queue）

3. 空间-时间权衡（Space-Time Tradeoff）

4. 原地修改（In-place Modification）

5. 分治法（Divide and Conquer）

6. 减少问题规模（Reduce Problem Size）

举一反三

1. 贪心算法（Greedy Algorithm）

2. 优先队列（Priority Queue）

3. 空间-时间权衡（Space-Time Tradeoff）

4. 原地修改（In-place Modification）

5. 分治法（Divide and Conquer）

6. 减少问题规模（Reduce Problem Size）

具体技巧和示例：

总结

题目链接

我的写法

# 读取输入
N, D = map(float, input().split())  # 读取月饼种类数N和市场最大需求量D，转换为浮点数
N = int(N)  # 将月饼种类数N转换为整数，因为月饼种类数不应该是小数
storages = list(map(float, input().split()))  # 读取每种月饼的库存量，并转换为浮点数
prices = list(map(float, input().split()))  # 读取每种月饼的总售价，并转换为浮点数

# 构建每种月饼的信息，包括库存量、总售价、和单位售价
# 注意月饼库存量和总售价可以是小数，初始三个参数可以都设为float型（测试点2）
infos = []
for i in range(N):  # 遍历每种月饼
    unit_price = prices[i] / storages[i]  # 计算每种月饼的单位售价（每吨售价）
    infos.append([storages[i], prices[i], unit_price])  # 将每种月饼的信息存入列表

# 按单位售价从高到低排序
infos.sort(key=lambda x: x[2], reverse=True)  # 按单位售价从高到低对月饼信息进行排序

output = 0.0  # 初始化输出的最大收益
for storage, total_price, unit_price in infos:  # 遍历排序后的月饼信息
    if D == 0.0:  # 如果市场需求量已经满足，退出循环
        break
    if storage <= D:  # 如果当前月饼的库存量小于等于剩余需求量
        output += total_price  # 将当前月饼的总售价加入收益
        D -= storage  # 减少相应的需求量
    else:  # 如果当前月饼的库存量大于剩余需求量
        output += D * unit_price  # 根据剩余需求量计算收益
        D = 0.0  # 将需求量设为0，表示已经满足需求

print(f"{output:.2f}")  # 输出最大收益，保留两位小数

这段代码实现了基于库存量和总售价的月饼销售策略，以最大化收益为目标。代码逻辑清晰，基本思路是先计算每种月饼的单位售价（即每吨售价），然后根据单位售价从高到低排序，优先销售单位售价高的月饼，以达到最大收益。以下是对这段代码的专业点评，以及其时间复杂度和空间复杂度的分析。

专业点评：

数据输入和预处理：
- 输入处理部分正确地将数据转换为浮点数，保证在处理涉及小数的计算时不会出现精度问题。
计算单位售价并排序：
- 通过计算每种月饼的单位售价并将其存储在列表中，排序时选择了基于单位售价从高到低的顺序，这一步很合理，因为单位售价高的月饼优先销售可以最大化总收益。
收益计算逻辑：

代码通过遍历排序后的月饼信息，根据库存量和剩余需求量更新总收益，逻辑清晰且高效。

时间复杂度分析：

输入读取和预处理：
- 读取和转换数据的时间复杂度为O(N)，因为需要对每一个输入数据进行处理。
计算单位售价并排序：
- 计算单位售价的时间复杂度为O(N)，因为需要对每一种月饼计算一次。
- 排序的时间复杂度为O(N log N)，因为使用了Timsort（Python内置的排序算法）。
收益计算：

遍历排序后的月饼信息，并根据需求量计算总收益，这部分时间复杂度为O(N)。

综合上述步骤，代码的总体时间复杂度为O(N log N)，这是因为排序是主要的时间消耗部分。

空间复杂度分析：

输入数据存储：
- 存储库存量和总售价需要两个长度为N的列表，空间复杂度为O(N)。
单位售价信息存储：

存储每种月饼的库存量、总售价和单位售价，空间复杂度为O(N)。

因此，总体空间复杂度为O(N)，因为存储每种月饼的信息占用了线性空间。

总结：

这段代码有效地解决了基于单位售价最大化收益的问题。时间复杂度主要由排序部分决定，为O(N log N)，而空间复杂度为O(N)，这是非常高效且合理的。可以进一步提高代码的健壮性，例如增加更多的错误处理和边界情况处理。总体上，这段代码在逻辑上是正确且高效的。

我要更强

在这段代码中，时间复杂度的主要瓶颈在于排序操作（O(N log N)），而空间复杂度是O(N)，主要是存储月饼信息。针对这两个方面，我们可以尝试一些优化方法。

时间复杂度优化：

如果月饼种类数很大，而市场需求量相对较小，可以采用优先队列（堆）来优化。我们可以使用最大堆来动态选择当前单位售价最高的月饼进行销售，从而避免全局排序，从而减少时间复杂度。

空间复杂度优化：

原地修改：将月饼的库存量、总售价、和单位售价等信息存储在原始列表中，避免额外的空间开销。

以下是结合这些优化后的代码示例，使用优先队列来改进时间复杂度，并在一定程度上降低空间复杂度。

import heapq

# 读取输入
N, D = map(float, input().split())
N = int(N)
storages = list(map(float, input().split()))
prices = list(map(float, input().split()))

# 创建一个最大堆存储每种月饼的单位售价及其相关信息
heap = []
for i in range(N):
    unit_price = prices[i] / storages[i]  # 计算单位售价
    heapq.heappush(heap, (-unit_price, storages[i], prices[i]))  # 使用负值构建最大堆

output = 0.0  # 初始化收益
while D > 0 and heap:  # 当市场需求量未满足且堆非空时
    unit_price, storage, total_price = heapq.heappop(heap)  # 弹出单位售价最高的月饼信息
    unit_price = -unit_price  # 将单位售价恢复为正值
    if storage <= D:  # 如果当前月饼库存量小于等于需求量
        output += total_price  # 将总售价加入收益
        D -= storage  # 减少相应的需求量
    else:  # 如果当前月饼库存量大于需求量
        output += D * unit_price  # 根据剩余需求量计算收益
        D = 0.0  # 将需求量设为0，表示需求已满足

print(f"{output:.2f}")  # 输出最终收益，保留两位小数