1357-每隔 n 个顾客打折

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

超市里正在举行打折活动，每隔 n 个顾客会得到 discount 的折扣。

超市里有一些商品，第 i 种商品为 products[i] 且每件单品的价格为 prices[i] 。

结账系统会统计顾客的数目，每隔 n 个顾客结账时，该顾客的账单都会打折，折扣为 discount （也就是如果原本账单为 x
，那么实际金额会变成 x - (discount * x) / 100 ），然后系统会重新开始计数。

顾客会购买一些商品， product[i] 是顾客购买的第 i 种商品， amount[i] 是对应的购买该种商品的数目。

请你实现 Cashier 类：

  • Cashier(int n, int discount, int[] products, int[] prices) 初始化实例对象，参数分别为打折频率 n ，折扣大小 discount ，超市里的商品列表 products 和它们的价格 prices 。
  • double getBill(int[] product, int[] amount) 返回账单的实际金额（如果有打折，请返回打折后的结果）。返回结果与标准答案误差在 10^-5 以内都视为正确结果。

示例 1：

**输入**
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
**输出**
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]
**解释**
Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);
cashier.getBill([1,2],[1,2]);                        // 返回 500.0, 账单金额为 = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]);                      // 返回 4000.0
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]);    // 返回 800.0 ，账单原本为 1600.0 ，但由于该顾客是第三位顾客，他将得到 50% 的折扣，所以实际金额为 1600 - 1600 * (50 / 100) = 800 。
cashier.getBill([4],[10]);                           // 返回 4000.0
cashier.getBill([7,3],[10,10]);                      // 返回 4000.0
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // 返回 7350.0 ，账单原本为 14700.0 ，但由于系统计数再次达到三，该顾客将得到 50% 的折扣，实际金额为 7350.0 。
cashier.getBill([2,3,5],[5,3,2]);                    // 返回 2500.0

提示：

  • 1 <= n <= 10^4
  • 0 <= discount <= 100
  • 1 <= products.length <= 200
  • 1 <= products[i] <= 200
  • products 列表中 不会 有重复的元素。
  • prices.length == products.length
  • 1 <= prices[i] <= 1000
  • 1 <= product.length <= products.length
  • product[i] 在 products 出现过。
  • amount.length == product.length
  • 1 <= amount[i] <= 1000
  • 最多有 1000 次对 getBill 函数的调用。
  • 返回结果与标准答案误差在 10^-5 以内都视为正确结果。

方法一：模拟

我们将所有的物品以及它们的价格存放进哈希映射（HashMap）中。对于哈希映射中的每个键值对，键表示物品的编号，值表示物品的价格，这样我们就可以方便快速地统计每一位顾客的消费金额了。

为了判断每一位顾客是否可以得到折扣，我们还需要使用一个计数器表示当前顾客的序号，如果该序号是 n 的倍数，我们就按照 discount 对顾客的消费金额进行打折。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Cashier {
private:
    unordered_map<int, int> price;
    int n, discount;
    int custom_id;
    
public:
    Cashier(int _n, int _d, vector<int>& products, vector<int>& prices): n(_n), discount(_d), custom_id(0) {
        for (int i = 0; i < products.size(); ++i) {
            price[products[i]] = prices[i];
        }
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        ++custom_id;
        double payment = 0;
        for (int i = 0; i < product.size(); ++i) {
            payment += price[product[i]] * amount[i];
        }
        if (custom_id % n == 0) {
            payment -= payment * discount / 100;
        }
        return payment;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Cashier:
    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
        self.price = dict()
        for product, price in zip(products, prices):
            self.price[product] = price
        self.n = n
        self.discount = discount
        self.custom_id = 0

    def getBill(self, product: List[int], amount: List[int]) -> float:
        self.custom_id += 1
        payment = 0.0
        for k, v in zip(product, amount):
            payment += self.price[k] * v
        if self.custom_id % self.n == 0:
            payment -= payment * self.discount / 100
        return payment

复杂度分析

  • 时间复杂度：预处理（Cashier 类的构造函数）的时间复杂度为 O(P)，其中 P 是数组 products 和 prices 的长度。getBill() 的时间复杂度为 O(M)，其中 M 是数组 product 和 amount 的长度。

  • 空间复杂度：预处理的空间复杂度为 O(P)。getBill() 的额外（预处理的结果之外）空间复杂度为 O(1)。

 Comments
On this page
1357-每隔 n 个顾客打折