Facade thanh toán

Đề bài

Mẫu thiết kế facade cung cấp một điểm vào đơn giản cho một hệ thống con phức tạp. Lệnh checkout của một cửa hàng ẩn hai hệ thống con: kho hàng và bảng giá.

Các mặt hàng được đánh số từ 0 đến n − 1. stock[i] là số lượng mặt hàng i hiện có và prices[i] là giá của nó. Giỏ hàng là một danh sách các dòng [item, quantity]; cùng một mặt hàng có thể xuất hiện ở nhiều dòng.

checkout(stock, prices, cart) phải:

Kiểm tra kho hàng: nếu tổng số lượng của bất kỳ mặt hàng nào trong giỏ lớn hơn số lượng tồn kho của nó, đơn hàng sẽ thất bại.
Ngược lại, trả về tổng giá của giỏ hàng.

Hãy cài đặt checkout_facade(stock, prices, cart).

Input

stock, prices: mỗi mảng có n giá trị.

cart: các dòng [item, quantity].

Output

Trả về tổng giá, hoặc -1 nếu bất kỳ mặt hàng nào không đủ tồn kho.

Ràng buộc

1 ≤ n ≤ 1,000

0 ≤ stock[i], prices[i] ≤ 100,000; 0 ≤ số dòng giỏ hàng ≤ 1,000; 1 ≤ quantity ≤ 1,000

Ví dụ

Ví dụ 1

Đầu vào:
cart = [
    [0, 2],
    [2, 4]
]
stock = [5, 2, 10]
prices = [3, 20, 1]

Kết quả mong đợi:
expected = 10

Đầu vào:
std::vector<std::vector<long long>> cart = {
    {0, 2},
    {2, 4}
};
std::vector<long long> stock = {5, 2, 10};
std::vector<long long> prices = {3, 20, 1};

Kết quả mong đợi:
long long expected = 10;

Đầu vào:
long[][] cart = new long[][] {
    new long[] {0, 2},
    new long[] {2, 4}
};
long[] stock = new long[] {5, 2, 10};
long[] prices = new long[] {3, 20, 1};

Kết quả mong đợi:
long expected = 10;

Giải thích

Cả hai mặt hàng đều còn trong kho. 2 × 3 + 4 × 1 = 10.

Ví dụ 2

Đầu vào:
cart = [
    [1, 1],
    [1, 2]
]
stock = [5, 2]
prices = [3, 20]

Kết quả mong đợi:
expected = -1

Đầu vào:
std::vector<std::vector<long long>> cart = {
    {1, 1},
    {1, 2}
};
std::vector<long long> stock = {5, 2};
std::vector<long long> prices = {3, 20};

Kết quả mong đợi:
long long expected = -1;

Đầu vào:
long[][] cart = new long[][] {
    new long[] {1, 1},
    new long[] {1, 2}
};
long[] stock = new long[] {5, 2};
long[] prices = new long[] {3, 20};

Kết quả mong đợi:
long expected = -1;

Giải thích

Mặt hàng 1 xuất hiện hai lần với tổng cộng 3 đơn vị, nhưng chỉ có 2 đơn vị trong kho, nên đơn hàng thất bại: -1.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Cộng số lượng của từng mặt hàng qua mọi dòng giỏ hàng trước.

Gợi ý 2

So các tổng đó với tồn kho trước khi tính bất kỳ giá nào.

Gợi ý 3

Nếu mặt hàng nào thiếu, trả về -1 ngay.

Độ phức tạp mong đợi

thời gian O(n + số dòng giỏ hàng), bộ nhớ phụ O(n)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Bạn sẽ học được gì

Đề bài

Input

Output

Ràng buộc

Ví dụ

Giải thích

Giải thích

Hướng tiếp cận

Tham khảo

Giải pháp cộng đồng