class Solution {
public:
long long waysToBuyPensPencils(int total, int cost1, int cost2) {
}
};
2240. 买钢笔和铅笔的方案数
给你一个整数 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原站题解
java 解法, 执行用时: 11 ms, 内存消耗: 38.3 MB, 提交时间: 2023-09-01 07:45:27
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;
}
}
php 解法, 执行用时: 152 ms, 内存消耗: 19.1 MB, 提交时间: 2023-09-01 07:42:34
class Solution {
/**
* @param Integer $total
* @param Integer $cost1
* @param Integer $cost2
* @return Integer
*/
function waysToBuyPensPencils($total, $cost1, $cost2) {
$ans = 0;
for ( $i = 0; $i <= intval($total/$cost1); $i++ ) {
$ans += intval(($total - $cost1 * $i) / $cost2) + 1;
}
return $ans;
}
}
javascript 解法, 执行用时: 120 ms, 内存消耗: 65.7 MB, 提交时间: 2022-12-05 18:11:56
/**
* @param {number} total
* @param {number} cost1
* @param {number} cost2
* @return {number}
*/
var waysToBuyPensPencils = function(total, cost1, cost2) {
if ( cost1 < cost2 ) {
[cost1, cost2] = [cost2, cost1];
}
return Array(Math.floor(total/cost1 + 1)).fill(0).reduce((a, _, i) => a + Math.floor(1 + (total - cost1 * i)/cost2), 0);
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-12-05 18:09:56
func waysToBuyPensPencils(total, cost1, cost2 int) int64 {
n := total/cost1 + 1
return int64(n + floorSum(n, cost2, -cost1, total))
}
// 返回 sum(floor((a*i+b)/m)), i 从 0 到 n-1
func floorSum(n, m, a, b int) (res int) {
if a < 0 {
a2 := a%m + m
res -= n * (n - 1) / 2 * ((a2 - a) / m)
a = a2
}
if b < 0 {
b2 := b%m + m
res -= n * ((b2 - b) / m)
b = b2
}
for {
if a >= m {
res += n * (n - 1) / 2 * (a / m)
a %= m
}
if b >= m {
res += n * (b / m)
b %= m
}
yMax := a*n + b
if yMax < m {
break
}
n = yMax / m
b = yMax % m
m, a = a, m
}
return
}
python3 解法, 执行用时: 660 ms, 内存消耗: 14.8 MB, 提交时间: 2022-12-05 18:09:35
class Solution:
def waysToBuyPensPencils(self, total: int, cost1: int, cost2: int) -> int:
ans = 0
for i in range(total//cost1 + 1):
ans += (total - cost1 * i) // cost2 + 1
return ans
golang 解法, 执行用时: 32 ms, 内存消耗: 1.8 MB, 提交时间: 2022-12-05 18:08:18
func waysToBuyPensPencils(total, cost1, cost2 int) (ans int64) {
for i := 0; i <= total/cost1; i++ {
ans += int64((total-cost1*i)/cost2) + 1 // 能买的铅笔个数 + 1
}
return
}