给你一个整数 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 <= 106
方法一：枚举
思路与算法
现在我们有 total 的钱数，一支钢笔的价格为 cost}_1，一支铅笔的价格为 cost}_2，现在我们需要求能购买的钢笔和铅笔的不同方案数目。
假设我们当前买了 x 支钢笔，满足 cost}_1 \times x \le \textit{total，则我们有 total} - \textit{cost}_1 \times x 的钱购买铅笔，则此时能购买的铅笔数可以为 0, 1, \dots, \Big\lfloor \dfrac{\textit{total} - \textit{cost}_1 \times x}{\textit{cost}_2} \Big\rfloor，即方案数为 \Big\lfloor \dfrac{\textit{total} - \textit{cost}_1 \times x}{\textit{cost}_2} \Big\rfloor + 1 种。那么我们枚举可以购买的钢笔数，然后对每一种情况分别计算可以购买的铅笔数并求和即为总的方案数目。
在代码实现的过程中，由于钢笔和铅笔的价格相互独立，所以为了降低平均时间复杂度，当 cost}_1 < \textit{cost}_2 时，我们将转换为枚举 cost}_2 来减少枚举次数。
代码
[sol1-Python3]1
2
3
4
5
6
7
8
9
| class Solution:
def waysToBuyPensPencils(self, total: int, cost1: int, cost2: int) -> int:
if cost1 < cost2:
return self.waysToBuyPensPencils(total, cost2, cost1)
res, cnt = 0, 0
while cnt * cost1 <= total:
res += (total - cnt * cost1) // cost2 + 1
cnt += 1
return res
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public long waysToBuyPensPencils(int total, int cost1, int cost2) {
if (cost1 < cost2) {
return waysToBuyPensPencils(total, cost2, cost1);
}
long res = 0, cnt = 0;
while (cnt * cost1 <= total) {
res += (total - cnt * cost1) / cost2 + 1;
cnt++;
}
return res;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
| public class Solution {
public long WaysToBuyPensPencils(int total, int cost1, int cost2) {
if (cost1 < cost2) {
return WaysToBuyPensPencils(total, cost2, cost1);
}
long res = 0, cnt = 0;
while (cnt * cost1 <= total) {
res += (total - cnt * cost1) / cost2 + 1;
cnt++;
}
return res;
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
long long waysToBuyPensPencils(int total, int cost1, int cost2) {
if (cost1 < cost2) {
return waysToBuyPensPencils(total, cost2, cost1);
}
long res = 0, cnt = 0;
while (cnt * cost1 <= total) {
res += (total - cnt * cost1) / cost2 + 1;
cnt++;
}
return res;
}
};
|
[sol1-Go]1
2
3
4
5
6
7
8
9
10
11
| func waysToBuyPensPencils(total int, cost1 int, cost2 int) int64 {
if cost1 < cost2 {
return waysToBuyPensPencils(total, cost2, cost1)
}
var res, cnt int
for cnt * cost1 <= total {
res += (total - cnt * cost1) / cost2 + 1
cnt++
}
return int64(res)
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
| var waysToBuyPensPencils = function(total, cost1, cost2) {
if (cost1 < cost2) {
return waysToBuyPensPencils(total, cost2, cost1);
}
let res = 0, cnt = 0;
while (cnt * cost1 <= total) {
res += parseInt((total - cnt * cost1) / cost2) + 1;
cnt++;
}
return res;
};
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
| long long waysToBuyPensPencils(int total, int cost1, int cost2){
if (cost1 < cost2) {
return waysToBuyPensPencils(total, cost2, cost1);
}
long long res = 0, cnt = 0;
while (cnt * cost1 <= total) {
res += (total - cnt * cost1) / cost2 + 1;
cnt++;
}
return res;
}
|
复杂度分析
