Medium

题目描述

给你一个整数 total ，表示你拥有的钱数。同时给你两个整数 cost1 和 cost2 ，分别表示钢笔和铅笔的价格。你可以花费你的一部分或者全部钱，去购买任意数目的两种笔。

请你返回购买钢笔和铅笔的 不同方案数目 。

示例 1：

输入：total = 20, cost1 = 10, cost2 = 5
输出：9
解释：钢笔价格为 10 ，铅笔价格为 5 。
- 如果你买 0 支钢笔，那么你可以买 0 ，1 ，2 ，3 或者 4 支铅笔。
- 如果你买 1 支钢笔，那么你可以买 0 ，1 或者 2 支铅笔。
- 如果你买 2 支钢笔，那么你没法买任何铅笔。
所以总共有 5 + 3 + 1 = 9 种购买方案。

示例 2：

输入：total = 5, cost1 = 10, cost2 = 10
输出：1
解释：钢笔和铅笔的价格都是 10 ，都比拥有的钱数多，所以你没法购买任何文具。所以只有 1 种购买方案：买 0 支钢笔和 0 支铅笔。

提示：

  • 1 <= total, cost1, cost2 <= 10^6

解题思路

这是一个典型的数学枚举问题，我们需要计算在给定预算下购买两种商品的不同方案数。

基本思路： 我们可以枚举其中一种商品的购买数量，然后计算另一种商品的可能购买数量。具体来说：

  1. 固定钢笔数量：遍历所有可能的钢笔购买数量（从0到 total/cost1）
  2. 计算铅笔数量：对于每个确定的钢笔数量，计算剩余资金可以购买的铅笔数量
  3. 累加方案数：将所有情况的方案数相加

优化考虑： 为了减少计算量，我们可以选择价格较高的商品作为枚举对象，这样枚举次数更少。

算法步骤：

  • 如果 cost1 > cost2，我们枚举钢笔数量
  • 否则，我们枚举铅笔数量
  • 对于每个固定的商品数量 i，剩余资金为 total - i * cost
  • 另一种商品的购买方案数为 (剩余资金 / 另一商品价格) + 1（包括0个的情况）

时间复杂度为 O(total/max(cost1,cost2))，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    long long waysToBuyPensPencils(int total, int cost1, int cost2) {
        long long result = 0;
        
        // 枚举价格较高的商品，减少枚举次数
        if (cost1 > cost2) {
            // 枚举钢笔数量
            for (int pens = 0; pens * cost1 <= total; pens++) {
                int remaining = total - pens * cost1;
                result += remaining / cost2 + 1;
            }
        } else {
            // 枚举铅笔数量
            for (int pencils = 0; pencils * cost2 <= total; pencils++) {
                int remaining = total - pencils * cost2;
                result += remaining / cost1 + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def waysToBuyPensPencils(self, total: int, cost1: int, cost2: int) -> int:
        result = 0
        
        # 枚举价格较高的商品，减少枚举次数
        if cost1 > cost2:
            # 枚举钢笔数量
            pens = 0
            while pens * cost1 <= total:
                remaining = total - pens * cost1
                result += remaining // cost2 + 1
                pens += 1
        else:
            # 枚举铅笔数量
            pencils = 0
            while pencils * cost2 <= total:
                remaining = total - pencils * cost2
                result += remaining // cost1 + 1
                pencils += 1
        
        return result

public class Solution {
    public long WaysToBuyPensPencils(int total, int cost1, int cost2) {
        long result = 0;
        
        // 枚举价格较高的商品，减少枚举次数
        if (cost1 > cost2) {
            // 枚举钢笔数量
            for (int pens = 0; pens * cost1 <= total; pens++) {
                int remaining = total - pens * cost1;
                result += remaining / cost2 + 1;
            }
        } else {
            // 枚举铅笔数量
            for (int pencils = 0; pencils * cost2 <= total; pencils++) {
                int remaining = total - pencils * cost2;
                result += remaining / cost1 + 1;
            }
        }
        
        return result;
    }
}

/**
 * @param {number} total
 * @param {number} cost1
 * @param {number} cost2
 * @return {number}
 */
var waysToBuyPensPencils = function(total, cost1, cost2) {
    let result = 0;
    
    // 枚举价格较高的商品，减少枚举次数
    if (cost1 > cost2) {
        // 枚举钢笔数量
        for (let pens = 0; pens * cost1 <= total; pens++) {
            const remaining = total - pens * cost1;
            result += Math.floor(remaining / cost2) + 1;
        }
    } else {
        // 枚举铅笔数量
        for (let pencils = 0; pencils * cost2 <= total; pencils++) {
            const remaining = total - pencils * cost2;
            result += Math.floor(remaining / cost1) + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(total/max(cost1,cost2)) - 枚举其中一种商品的所有可能购买数量
空间复杂度O(1) - 只使用常数额外空间

相关题目