【LeetCode - 每日一题】2240. 买钢笔和铅笔的方案数（23.09.1）

2240. 买钢笔和铅笔的方案数

题意

• 两种价格的笔
• 返回所有可以买的方案数
• 可以为 0

解法

注意这道题的复杂度比较高，O(N²) 是过不了的。一开始是这样写的：

// tle 代码
class Solution {
public:long long waysToBuyPensPencils(int total, int cost1, int cost2) {int max1 = total / cost1;int max2 = total / cost2;long long ans = 0;for(int i = 0; i <= max1; i++){for(int j = 0; j <= max2; j++){if(i * cost1 + j * cost2 <= total)ans++;}}return ans;}
};

但是在极端情况，比如 cost1 = cost2 = 1 的时候，两重 for 循环的复杂度会达到O(N²)，因此直接在每次拿取若干支钢笔时计算可以拿的铅笔的方案数（注意可以拿 0 只 铅笔）。

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

复杂度

时间复杂度：O($\lceil \frac{total}{cost1}\rceil$)，可以优化为 O($max(\lceil \frac{total}{cost1}\rceil ,\lceil \frac{total}{cost2}\rceil )$)。
空间复杂度：O(1)。

---