Question

1357. 每隔 n 个顾客打折

English Version

题目描述

超市里正在举行打折活动，每隔 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 以内都视为正确结果。

解法

方法一：哈希表 + 模拟

用哈希表 $d$ 存储商品编号和价格，然后遍历商品编号和数量，计算总价，再根据折扣计算折扣后的价格。

初始化的时间复杂度为 $O(n)$，其中 $n$ 为商品的数量。getBill 函数的时间复杂度为 $O(m)$，其中 $m$ 为购买商品的数量。空间复杂度为 $O(n)$。

class Cashier:
  def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
    self.i = 0
    self.n = n
    self.discount = discount
    self.d = {product: price for product, price in zip(products, prices)}

  def getBill(self, product: List[int], amount: List[int]) -> float:
    self.i += 1
    discount = self.discount if self.i % self.n == 0 else 0
    ans = 0
    for p, a in zip(product, amount):
      x = self.d[p] * a
      ans += x - (discount * x) / 100
    return ans


# Your Cashier object will be instantiated and called as such:
# obj = Cashier(n, discount, products, prices)
# param_1 = obj.getBill(product,amount)

class Cashier {
  private int i;
  private int n;
  private int discount;
  private Map<Integer, Integer> d = new HashMap<>();

  public Cashier(int n, int discount, int[] products, int[] prices) {
    this.n = n;
    this.discount = discount;
    for (int j = 0; j < products.length; ++j) {
      d.put(products[j], prices[j]);
    }
  }

  public double getBill(int[] product, int[] amount) {
    int dis = (++i) % n == 0 ? discount : 0;
    double ans = 0;
    for (int j = 0; j < product.length; ++j) {
      int p = product[j], a = amount[j];
      int x = d.get(p) * a;
      ans += x - (dis * x) / 100.0;
    }
    return ans;
  }
}

/**
 * Your Cashier object will be instantiated and called as such:
 * Cashier obj = new Cashier(n, discount, products, prices);
 * double param_1 = obj.getBill(product,amount);
 */

class Cashier {
public:
  Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
    this->n = n;
    this->discount = discount;
    for (int j = 0; j < products.size(); ++j) {
      d[products[j]] = prices[j];
    }
  }

  double getBill(vector<int> product, vector<int> amount) {
    int dis = (++i) % n == 0 ? discount : 0;
    double ans = 0;
    for (int j = 0; j < product.size(); ++j) {
      int x = d[product[j]] * amount[j];
      ans += x - (dis * x) / 100.0;
    }
    return ans;
  }

private:
  int i = 0;
  int n;
  int discount;
  unordered_map<int, int> d;
};

/**
 * Your Cashier object will be instantiated and called as such:
 * Cashier* obj = new Cashier(n, discount, products, prices);
 * double param_1 = obj->getBill(product,amount);
 */

type Cashier struct {
  i    int
  n    int
  discount int
  d    map[int]int
}

func Constructor(n int, discount int, products []int, prices []int) Cashier {
  d := map[int]int{}
  for i, product := range products {
    d[product] = prices[i]
  }
  return Cashier{0, n, discount, d}
}

func (this *Cashier) GetBill(product []int, amount []int) (ans float64) {
  this.i++
  dis := 0
  if this.i%this.n == 0 {
    dis = this.discount
  }
  for j, p := range product {
    x := float64(this.d[p] * amount[j])
    ans += x - (float64(dis)*x)/100.0
  }
  return
}

/**
 * Your Cashier object will be instantiated and called as such:
 * obj := Constructor(n, discount, products, prices);
 * param_1 := obj.GetBill(product,amount);
 */