跳转至

1357. 每隔 n 个顾客打折

题目描述

超市里正在举行打折活动,每隔 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\) 存储每件商品的编号和单价,在初始化时将 productsprices 一一对应存入哈希表。

同时维护一个顾客计数器 \(i\),初始值为 \(0\)

对于 getBill 操作:

  1. 将计数器加一并取模:\(i = (i + 1) \bmod n\),表示当前是第几位顾客结账;
  2. 遍历本次购买的商品编号和数量,计算账单总额 \(x = \sum_j d[\textit{product}[j]] \times \textit{amount}[j]\)
  3. \(i = 0\),说明当前顾客是第 \(n\) 位顾客,应对整单打折,返回 \(x - \dfrac{\textit{discount} \times x}{100}\);否则直接返回 \(x\)

初始化的时间复杂度为 \(O(n)\),其中 \(n\) 为商品种类数。每次 getBill 的时间复杂度为 \(O(m)\),其中 \(m\) 为本次购买商品的种类数。空间复杂度为 \(O(n)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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 = {a: b for a, b in zip(products, prices)}

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


# Your Cashier object will be instantiated and called as such:
# obj = Cashier(n, discount, products, prices)
# param_1 = obj.getBill(product,amount)
 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
26
27
28
29
30
31
32
33
34
class Cashier {
    private int i;
    private int n;
    private int discount;
    private Map<Integer, Integer> d;

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

    public double getBill(int[] product, int[] amount) {
        this.i = (this.i + 1) % this.n;
        double x = 0;
        for (int j = 0; j < product.length; j++) {
            x += this.d.get(product[j]) * amount[j];
        }
        if (this.i == 0) {
            return x - (this.discount * x) / 100.0;
        }
        return x;
    }
}

/**
 * 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);
 */
 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
26
27
28
29
30
31
32
33
34
class Cashier {
public:
    int i;
    int n;
    int discount;
    unordered_map<int, int> d;

    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
        this->i = 0;
        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) {
        i = (i + 1) % n;
        double x = 0;
        for (int j = 0; j < product.size(); j++) {
            x += d[product[j]] * amount[j];
        }
        if (i == 0) {
            return x - (discount * x) / 100.0;
        }
        return x;
    }
};

/**
 * 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);
 */
 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
26
27
28
29
30
31
32
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 := make(map[int]int)
    for i := 0; i < len(products); i++ {
        d[products[i]] = prices[i]
    }
    return Cashier{i: 0, n: n, discount: discount, d: d}
}

func (this *Cashier) GetBill(product []int, amount []int) float64 {
    this.i = (this.i + 1) % this.n
    x := 0
    for i := 0; i < len(product); i++ {
        x += this.d[product[i]] * amount[i]
    }
    if this.i == 0 {
        return float64(x) - float64(this.discount)*float64(x)/100.0
    }
    return float64(x)
}

/**
 * Your Cashier object will be instantiated and called as such:
 * obj := Constructor(n, discount, products, prices);
 * param_1 := obj.GetBill(product,amount);
 */
 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
26
27
28
29
30
31
32
33
34
class Cashier {
    i: number;
    n: number;
    discount: number;
    d: Map<number, number>;

    constructor(n: number, discount: number, products: number[], prices: number[]) {
        this.i = 0;
        this.n = n;
        this.discount = discount;
        this.d = new Map();
        for (let j = 0; j < products.length; j++) {
            this.d.set(products[j], prices[j]);
        }
    }

    getBill(product: number[], amount: number[]): number {
        this.i = (this.i + 1) % this.n;
        let x = 0;
        for (let j = 0; j < product.length; j++) {
            x += (this.d.get(product[j]) || 0) * amount[j];
        }
        if (this.i === 0) {
            return x - (this.discount * x) / 100;
        }
        return x;
    }
}

/**
 * Your Cashier object will be instantiated and called as such:
 * var obj = new Cashier(n, discount, products, prices)
 * var param_1 = obj.getBill(product,amount)
 */
 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
use std::cell::Cell;
use std::collections::HashMap;

struct Cashier {
    i: Cell<i32>,
    n: i32,
    discount: i32,
    d: HashMap<i32, i32>,
}

impl Cashier {
    fn new(n: i32, discount: i32, products: Vec<i32>, prices: Vec<i32>) -> Self {
        let mut d = HashMap::new();
        for i in 0..products.len() {
            d.insert(products[i], prices[i]);
        }
        Cashier {
            i: Cell::new(0),
            n,
            discount,
            d,
        }
    }

    fn get_bill(&self, product: Vec<i32>, amount: Vec<i32>) -> f64 {
        let mut x = 0i64;
        let mut i = self.i.get();
        i = (i + 1) % self.n;
        self.i.set(i);

        for j in 0..product.len() {
            x += (self.d[&product[j]] as i64) * (amount[j] as i64);
        }

        if i == 0 {
            return x as f64 - (self.discount as f64) * (x as f64) / 100.0;
        }
        x as f64
    }
}

// Your Cashier object will be instantiated and called as such:
// let obj = Cashier::new(n, discount, products, prices);
// let ret_1: f64 = obj.get_bill(product, amount);

评论