2240. 买钢笔和铅笔的方案数-Toy模板网

这篇具有很好参考价值的文章主要介绍了2240. 买钢笔和铅笔的方案数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tag

【枚举】【数学】【2023-09-01】

题目来源

2240. 买钢笔和铅笔的方案数 2240. 买钢笔和铅笔的方案数,LeetCode每日一题,数学,枚举,算法,c++

题目解读

现在你有一笔钱 total，用来购买钢笔和铅笔，它们的价格分别为 cost1 和 cost2，试问你可以有多少种不同的购买方案。其中，出现的价格与钱数都是整数，购买笔的数量可以是任意数目（包括 0）。

解题思路

方法一：枚举

我们拥有的这笔钱最多可以买 $\lfloor \frac{total}{cost1} \rfloor$ 支钢笔，加上可以买 0 支钢笔，那么我们买钢笔的方案数为 $\lfloor \frac{total}{cost1} \rfloor$ 。

现在我们枚举可以买的钢笔的数量 i，则 $\lfloor \frac{total - i*cost1}{cost2} \rfloor$ 表示买了 i 支钢笔的情况下剩下的钱可以买的铅笔的数量，也表示此时的方案数（不包括买 0 支铅笔的情况），那么 $\lfloor \frac{total - i*cost1}{cost2} \rfloor$ 则表示买了 i 支钢笔时的方案数（包括买 0 支铅笔的情况），于是总的方案数为：

$\sum_{i=0}^{\lfloor \frac{total}{cost1} \rfloor}{\left( 1+\lfloor \frac{total-i\times cost1}{cost2} \rfloor \right)}$

实现代码

class Solution {
public:
    long long waysToBuyPensPencils(int total, int cost1, int cost2) {
        long long n = 1 + total / cost1, res = 0;
        for (long long i = 0; i < n; ++i) {
            res += 1 + (total - cost1 * i) / cost2;
        }
        return res;
    }
};