【枚举】【数学】
现在你有一笔钱 total，用来购买钢笔和铅笔，它们的价格分别为 cost1 和 cost2，试问你可以有多少种不同的购买方案。其中，出现的价格与钱数都是整数，购买笔的数量可以是任意数目（包括 0）。
我们拥有的这笔钱最多可以买
⌊
t
o
t
a
l
c
o
s
t
1
⌋
\lfloor \frac{total}{cost1} \rfloor
⌊cost1total⌋ 支钢笔，加上可以买 0 支钢笔，那么我们买钢笔的方案数为
1
+
⌊
t
o
t
a
l
c
o
s
t
1
⌋
1 + \lfloor \frac{total}{cost1} \rfloor
1+⌊cost1total⌋。
现在我们枚举可以买的钢笔的数量 i，则
⌊
t
o
t
a
l
−
i
∗
c
o
s
t
1
c
o
s
t
2
⌋
\lfloor \frac{total - i*cost1}{cost2} \rfloor
⌊cost2total−i∗cost1⌋ 表示买了 i 支钢笔的情况下剩下的钱可以买的铅笔的数量，也表示此时的方案数（不包括买 0 支铅笔的情况），那么
1
+
⌊
t
o
t
a
l
−
i
∗
c
o
s
t
1
c
o
s
t
2
⌋
1 + \lfloor \frac{total - i*cost1}{cost2} \rfloor
1+⌊cost2total−i∗cost1⌋ 则表示买了 i 支钢笔时的方案数（包括买 0 支铅笔的情况），于是总的方案数为：
∑ i = 0 ⌊ t o t a l c o s t 1 ⌋ ( 1 + ⌊ t o t a l − i × c o s t 1 c o s t 2 ⌋ ) \sum_{i=0}^{\lfloor \frac{total}{cost1} \rfloor}{\left( 1+\lfloor \frac{total-i\times cost1}{cost2} \rfloor \right)} i=0∑⌊cost1total⌋(1+⌊cost2total−i×cost1⌋)
实现代码
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;
}
};
时间复杂度： O ( ⌊ t o t a l c o s t 1 ⌋ ) O(\lfloor \frac{total}{cost1} \rfloor) O(⌊cost1total⌋)。
空间复杂度： O ( 1 ) O(1) O(1)。
以上就是本篇文章的内容了，感谢您的阅读。