拍卖干草：如何定价才能收益最大化？

好的，我们先一步步分析这个问题，然后给出解决方案。 --- ## 🧠 问题理解 - **m**：干草的批数（库存量）。 - **n**：顾客的数量。 - **ai**：第 i 个顾客的报价（愿意为 1 批干草支付的价格）。 - **规则**： 1. John 设定一个**单价** `p`。 2. 所有报价 `ai >= p` 的顾客，每人会买 1 批干草。 3. 如果满足条件的顾客数量 > m，则只有 m 批可卖（即最多卖给 m 个顾客）。 4. 总收益 = `p * min(满足条件的顾客数, m)`。 5. 目标：选择 `p`，使总收益最大。若收益相同，选最小的 `p`。 --- ## 📊 思路分析 1. 顾客的报价 `ai` 是给定的，单价 `p` 必须等于某个顾客的报价（或者介于报价之间），因为： - 如果 `p` 在两个报价之间，降低 `p` 到下一个报价值，顾客数量不变，总收益会减少（因为单价降低），所以最优单价一定是某个 `ai`。 - 因此我们只需要考虑 `p` 取 `ai` 的值即可。 2. 步骤： - 将 `ai` 从大到小排序。 - 遍历排序后的报价，假设当前报价作为单价 `p`，那么所有报价 >= `p` 的顾客就是当前及之前遍历过的顾客（因为排序是从大到小）。 - 设当前是第 `i` 个顾客（从 1 开始数），那么满足条件的顾客数 = `i`。 - 实际卖出的数量 = `min(i, m)`。 - 收益 = `p * min(i, m)`。 - 记录最大收益及对应的单价。 3. 注意：如果有多个 `p` 得到相同最大收益，要选最小的 `p`。由于我们是从大到小遍历，当收益相后遇到的 `p` 更小，所以应该更新为更小的 `p`。 --- ## 🧮 样例推演 输入： ``` m = 5, n = 4 报价：2 8 10 7 ``` 排序（从大到小）： ``` 10 8 7 2 ``` 遍历： - i=1, p=10, 人数=1, 卖出=min(1,5)=1, 收益=10*1=10 - i=2, p=8, 人数=2, 卖出=min(2,5)=2, 收益=8*2=16 - i=3, p=7, 人数=3, 卖出=min(3,5)=3, 收益=7*3=21 - i=4, p=2, 人数=4, 卖出=min(4,5)=4, 收益=2*4=8 最大收益 21，对应 p=7。 --- ## 💻 代码实现（Python） ```python # 读取输入 m, n = map(int, input().split()) a = list(map(int, input().split())) # 从大到小排序 a.sort(reverse=True) max_profit = 0 best_price = 0 # 遍历每个可能的单价（即排序后的每个报价） for i in range(n): price = a[i] # 当前报价作为单价时，满足条件的顾客数 = i+1 customers = i + 1 sell_count = min(customers, m) profit = price * sell_count # 如果收益更大，更新；如果收益相等，选择更小的单价（因为排序从大到小，后面遇到的 price 更小） if profit > max_profit or (profit == max_profit and price < best_price): max_profit = profit best_price = price print(best_price, max_profit) ``` --- ## ⚙️ 复杂度分析 - 排序：O(n log n) - 遍历：O(n) - 总复杂度：O(n log n)，在 n ≤ 5000 时非常快。 --- ## 🛡️ 边界情况与测试 1. **n = 1**：只有一个顾客，单价就是他的报价，收益 = min(1, m) * 报价。 2. **m ≥ n**：库存充足，所有满足条件的顾客都能买到，收益 = 单价 * 满足人数。 3. **所有报价相同**：收益 = 单价 * min(n, m)，单价就是该报价。 4. **单价很低**：可能所有顾客都买，但收益不一定最大。 --- ## 📝 开发建议 1. **输入处理**：注意数据范围，n ≤ 5000，用 Python 的 `list` 和内置排序足够。 2. **变量命名**：使用有意义的变量名，如 `best_price`, `max_profit`，提高可读性。 3. **比较逻辑**：收益相等时选更小的单价，这个判断要小心，确保遍历顺序能自然得到最小单价。 4. **测试**：自己构造几个小例子验证，比如 m=1 或 m 很大的情况。 --- ######[AI写代码神器 | 1171点数解答 | 2026-02-23 21:10:09]