Medium

题目描述

给定五个整数 cost1, cost2, costBoth, need1 和 need2。

有三种类型的物品可供购买：

  • 第1类物品：成本为 cost1，仅对类型1需求贡献1个单位
  • 第2类物品：成本为 cost2，仅对类型2需求贡献1个单位
  • 第3类物品：成本为 costBoth，同时对类型1和类型2需求各贡献1个单位

你必须收集足够的物品，使得对类型1的总贡献至少为 need1，对类型2的总贡献至少为 need2。

返回达成这些需求的最小总成本。

示例 1：

输入：cost1 = 3, cost2 = 2, costBoth = 1, need1 = 3, need2 = 2
输出：3
解释：购买3个第3类物品，成本为 3 * 1 = 3，对类型1的总贡献为3（>= need1 = 3），对类型2的总贡献为3（>= need2 = 2）。
任何其他有效组合的成本都会更高，因此最小总成本为3。

示例 2：

输入：cost1 = 5, cost2 = 4, costBoth = 15, need1 = 2, need2 = 3
输出：22
解释：购买 need1 = 2 个第1类物品和 need2 = 3 个第2类物品：2 * 5 + 3 * 4 = 10 + 12 = 22。
任何其他有效组合的成本都会更高，因此最小总成本为22。

示例 3：

输入：cost1 = 5, cost2 = 4, costBoth = 15, need1 = 0, need2 = 0
输出：0
解释：由于不需要任何物品（need1 = need2 = 0），我们什么都不买，支付0。

约束条件：

  • 1 <= cost1, cost2, costBoth <= 10^6
  • 0 <= need1, need2 <= 10^9

解题思路

这是一个典型的贪心算法问题。我们需要分析不同购买策略的成本效益。

思路分析：

  1. 基本策略：我们有三种购买方式

    • 分别购买第1类和第2类物品
    • 优先购买第3类物品（同时满足两种需求）
    • 混合购买

  2. 关键观察：第3类物品的性价比取决于它与分别购买两类物品的成本对比

    • 如果 costBoth < cost1 + cost2，则第3类物品更划算
    • 对于重叠的需求部分 min(need1, need2)，优先考虑成本更低的方案

  3. 贪心策略：

    • 首先处理两种需求的重叠部分：选择 min(costBoth, cost1 + cost2) 的方案
    • 然后处理剩余的单独需求：
      • 剩余的类型1需求：选择 min(costBoth, cost1)
      • 剩余的类型2需求：选择 min(costBoth, cost2)

  4. 实现细节：

    • 计算重叠需求：overlap = min(need1, need2)
    • 计算剩余需求：rem1 = need1 - overlap, rem2 = need2 - overlap
    • 总成本 = 重叠部分成本 + 剩余部分成本

这种贪心策略能保证全局最优解，因为我们在每个阶段都选择了成本最低的方案。

代码实现

class Solution {
public:
    long long minimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
        if (need1 == 0 && need2 == 0) return 0;
        
        long long overlap = min(need1, need2);
        long long rem1 = need1 - overlap;
        long long rem2 = need2 - overlap;
        
        long long totalCost = 0;
        
        // Handle overlap with minimum cost strategy
        totalCost += overlap * min(costBoth, cost1 + cost2);
        
        // Handle remaining need1
        totalCost += rem1 * min(costBoth, cost1);
        
        // Handle remaining need2
        totalCost += rem2 * min(costBoth, cost2);
        
        return totalCost;
    }
};

class Solution:
    def minimumCost(self, cost1: int, cost2: int, costBoth: int, need1: int, need2: int) -> int:
        if need1 == 0 and need2 == 0:
            return 0
        
        overlap = min(need1, need2)
        rem1 = need1 - overlap
        rem2 = need2 - overlap
        
        total_cost = 0
        
        # Handle overlap with minimum cost strategy
        total_cost += overlap * min(costBoth, cost1 + cost2)
        
        # Handle remaining need1
        total_cost += rem1 * min(costBoth, cost1)
        
        # Handle remaining need2
        total_cost += rem2 * min(costBoth, cost2)
        
        return total_cost

public class Solution {
    public long MinimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
        if (need1 == 0 && need2 == 0) return 0;
        
        long overlap = Math.Min(need1, need2);
        long rem1 = need1 - overlap;
        long rem2 = need2 - overlap;
        
        long totalCost = 0;
        
        // Handle overlap with minimum cost strategy
        totalCost += overlap * Math.Min(costBoth, cost1 + cost2);
        
        // Handle remaining need1
        totalCost += rem1 * Math.Min(costBoth, cost1);
        
        // Handle remaining need2
        totalCost += rem2 * Math.Min(costBoth, cost2);
        
        return totalCost;
    }
}

/**
 * @param {number} cost1
 * @param {number} cost2
 * @param {number} costBoth
 * @param {number} need1
 * @param {number} need2
 * @return {number}
 */
var minimumCost = function(cost1, cost2, costBoth, need1, need2) {
    let minCost = Infinity;
    
    for (let both = 0; both <= Math.max(need1, need2); both++) {
        let remaining1 = Math.max(0, need1 - both);
        let remaining2 = Math.max(0, need2 - both);
        
        let totalCost = both * costBoth + remaining1 * cost1 + remaining2 * cost2;
        minCost = Math.min(minCost, totalCost);
    }
    
    return minCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(1) - 只需要常数时间的数学计算
空间复杂度O(1) - 只使用常数额外空间