pta月饼 样例
时间: 2025-03-19 20:05:36 浏览: 43
### PTA 月饼问题解析
PTA上的月饼问题是典型的贪心算法应用案例。以下是基于给定引用内容和专业知识对该问题的详细分析。
#### 贪心策略的核心思想
该问题的关键在于通过计算每种月饼的单价(即总售价除以库存量),并按照单价从高到低排序来决定销售顺序[^1]。这样可以确保在有限的需求下获得最大的收益。
#### 输入与输出描述
每个输入包含一个测试用例,其中:
- 第一行提供两个正整数 \(N\) 和 \(D\),分别代表月饼种类数量和市场最大需求量。
- 接下来的两行分别是每种月饼的库存量和对应的总售价。
程序应输出能够达到的最大收入值,保留两位小数[^2]。
#### 示例代码实现
下面是一个完整的 Python 实现方案:
```python
def main():
import sys
# 获取输入数据
line = input().strip()
N, D = map(int, line.split())
stocks = list(map(float, input().split()))
values = list(map(float, input().split()))
# 计算每类月饼的单位价值
ratios = [(values[i]/stocks[i], i) for i in range(N)]
ratios.sort(reverse=True)
total_profit = 0.0
demand_left = D
for ratio, idx in ratios:
if demand_left <= 0:
break
amount_to_sell = min(stocks[idx], demand_left)
total_profit += amount_to_sell * (values[idx] / stocks[idx])
demand_left -= amount_to_sell
print("%.2f" % total_profit)
if __name__ == "__main__":
main()
```
上述代码实现了如下逻辑流程:
1. **读取输入**:获取月饼种类数目、市场需求总量以及各类型的库存量和总售价。
2. **构建比率列表**:对于每一类月饼,计算其单位重量的价值,并按降序排列这些比率。
3. **模拟销售过程**:依次尝试卖出最高性价比的月饼直到满足全部需求或无更多可用资源为止。
4. **结果输出**:最终打印所得总收入至标准输出流,保持精度为两位小数。
#### 特殊情况处理
需要注意的是,在某些情况下可能出现当前剩余需求超过了任何一种现存月饼的数量之和的情形。此时需特别注意循环终止条件设置合理范围防止越界访问错误发生。
阅读全文
相关推荐

















