Braze

01Shopping Cart Billing

An e-commerce company is currently celebrating ten years in business. They are having a sale to honor their privileged members, those who have been using their services for the past five years. They receive the best discounts indicated by any discount tags attached to the product. Determine the minimum cost to purchase all products listed. As each potential price is calculated, truncate it to its integer part before adding it to the total. Return the cost to purchase all items as an integer. There are three types of discount tags: Type 0: discounted price, the item is sold for a given price. Type 1: percentage discount, the customer is given a fixed percentage discount from the retail price. Type 2: fixed discount, the customer is given a fixed amount off from the retail price. Function Description Complete the function findLowestPrice in the editor below. findLowestPrice has the following parameter(s):

String[][] products: a 2D array of product descriptors as strings: price followed by up to m-1 discount tags
String[][] discounts: a 2D array of tag descriptors as strings: tag, type, amount Returns int: the total amount paid for all listed products, discounted to privileged members' pricing

Constraints

1 ≤ n, m, d ≤ 1000
tags are not unique

解法

把 discounts 预处理为 tag -> (type, amount) 映射。同一标签可能多次出现，取其能给出的最优价格的那个。对每个商品，从基础价开始，枚举它带的所有 tag，按规则计算折后价(type 0 取折扣价、type 1 按百分比、type 2 减固定额)，并向下取整。最后累加。复杂度 O(n·m + d)，空间 O(d)。

from typing import List
from math import floor

def find_lowest_price(products: List[List[str]], discounts: List[List[str]]) -> int:
    tag_map = {}
    for tag, t, amt in discounts:
        tag_map.setdefault(tag, []).append((int(t), float(amt)))
    total = 0
    for row in products:
        price = float(row[0])
        best = price
        for tag in row[1:]:
            if tag not in tag_map:
                continue
            for t, amt in tag_map[tag]:
                if t == 0:
                    cand = amt
                elif t == 1:
                    cand = price * (100 - amt) / 100.0
                else:
                    cand = price - amt
                if cand < best:
                    best = cand
        total += int(best)
    return total

import java.util.*;

class Solution {
    int findLowestPrice(String[][] products, String[][] discounts) {
        Map<String, List<double[]>> tagMap = new HashMap<>();
        for (String[] d : discounts) {
            tagMap.computeIfAbsent(d[0], k -> new ArrayList<>())
                  .add(new double[]{Double.parseDouble(d[1]), Double.parseDouble(d[2])});
        }
        long total = 0;
        for (String[] row : products) {
            double price = Double.parseDouble(row[0]);
            double best = price;
            for (int i = 1; i < row.length; i++) {
                List<double[]> rules = tagMap.get(row[i]);
                if (rules == null) continue;
                for (double[] r : rules) {
                    double cand;
                    int t = (int) r[0];
                    double amt = r[1];
                    if (t == 0) cand = amt;
                    else if (t == 1) cand = price * (100 - amt) / 100.0;
                    else cand = price - amt;
                    if (cand < best) best = cand;
                }
            }
            total += (long) Math.floor(best);
        }
        return (int) total;
    }
}

class Solution {
public:
    int findLowestPrice(vector<vector<string>>& products, vector<vector<string>>& discounts) {
        unordered_map<string, vector<pair<int, double>>> tagMap;
        for (auto& d : discounts) {
            tagMap[d[0]].push_back({stoi(d[1]), stod(d[2])});
        }
        long long total = 0;
        for (auto& row : products) {
            double price = stod(row[0]);
            double best = price;
            for (size_t i = 1; i < row.size(); ++i) {
                auto it = tagMap.find(row[i]);
                if (it == tagMap.end()) continue;
                for (auto& [t, amt] : it->second) {
                    double cand;
                    if (t == 0) cand = amt;
                    else if (t == 1) cand = price * (100 - amt) / 100.0;
                    else cand = price - amt;
                    if (cand < best) best = cand;
                }
            }
            total += (long long) floor(best);
        }
        return (int) total;
    }
};