2023-04-02：设计一个仓库管理器，提供如下的方法：
1) void supply(String item, int num, int price)
名字叫item的商品，个数num，价格price。
2) int sell(String item, int num)
卖出叫item的商品，个数num个，价格从低到高，返回卖出总价。
如果商品很多，每种商品的数量可能很多，该怎么设计这个结构。

答案2023-04-02：

设计思路

我们需要设计一个仓库管理器，它可以支持以下几种操作：

1.向指定商品中进货一定数量的货物；
2.对指定商品进行售卖，并返回售卖的总价。

为了实现这些功能，我们需要对每种商品维护一个最大堆，堆中存储的是该商品的所有不同价格，按照从低到高的顺序排列。同时，我们还需要一个哈希表，记录每个价格对应的商品数量。

在进货时，我们首先根据传入的商品名称，在哈希表中查找是否已经有该商品信息。如果有，则直接将新货物数量加入相应的价格中；否则，我们就需要创建一个新的最大堆和哈希表项，并将新货物信息添加到其中。

在售卖时，我们需要按照从低到高的价格顺序逐个处理商品。具体来说，我们从最大堆中弹出最低价格的商品，然后查询其数量是否足够售卖。如果数量足够，那么我们将相应的金额累加到总价中，并从哈希表中删除对应的价格项；否则，我们只能将部分商品出售，并将剩余商品放回最大堆中，等待下一次处理。

主要数据结构

为了实现上述功能，我们需要使用以下几种数据结构：

1.哈希表（HashMap）：用于记录每个商品的价格和数量信息；
2.最大堆（BinaryHeap）：存储每个商品的所有不同价格，并按照从低到高的顺序排列。

具体实现

在 Rust 中，我们可以通过定义一个名为 Store 的结构体来表示每种商品的价格数量信息。该结构体包含两个字段：

1.price_nums：本质上是一个哈希表，记录了每个价格对应的商品数量；
2.heap：是一个最大堆，存储了所有不同价格的商品，便于在售卖时按照价格从低到高进行处理。

struct Store {
    price_nums: HashMap<i32, i32>,
    heap: BinaryHeap<i32>,
}

impl Store {
    fn new() -> Self {
        Self {
            price_nums: HashMap::new(),
            heap: BinaryHeap::new(),
        }
    }

    fn add(&mut self, num: i32, price: i32) {
        if let Some(count) = self.price_nums.get_mut(&price) {
            *count += num;
        } else {
            self.price_nums.insert(price, num);
            self.heap.push(price);
        }
    }

    fn remove(&mut self, mut num: i32) -> i32 {
        let mut money = 0;
        while !self.heap.is_empty() && num != 0 {
            let price = self.heap.pop().unwrap();
            let stores = *self.price_nums.get(&price).unwrap();

            if num >= stores {
                money += price * stores;
                self.price_nums.remove(&price);
                num -= stores;
            } else {
                money += price * num;
                self.heap.push(price);
                self.price_nums.insert(price, stores - num);
                break;
            }
        }
        money
    }
}

接下来，我们可以定义一个名为 StoreManager 的结构体，用于管理所有商品的进货和售出操作。该结构体包含一个哈希表 map，键是商品名称，值是对应的 Store 对象。

pub struct StoreManager {
    map: HashMap<String, Store>,
}

在 supply 方法中，我们根据传入的商品名称在哈希表中查找是否已经有该商品信息。如果有，则直接将新货物数量加入相应的价格中；否则，我们就需要创建一个新的最大堆和哈希表项，并将新货物信息添加到其中。

在 sell 方法中，我们首先通过商品名称找到对应的 Store 对象，然后调用其 remove 方法进行售卖操作。在这个方法里，我们首先从最大堆中弹出价格最低的商品，然后查看其数量是否足够售卖。如果该商品数量大于等于需要售卖的数量，那么直接将总价增加相应的金额，并删除该商品；否则将总价增加当前售卖所需的金额，并将剩余的商品放回最大堆中。

impl StoreManager {
    pub fn supply(&mut self, item: &str, num: i32, price: i32) {
        let store = self.map.entry(item.to_string()).or_insert(Store::new());
        store.add(num, price);
    }

    pub fn sell(&mut self, item: &str, num: i32) -> i32 {
        self.map.get_mut(item).unwrap().remove(num)
    }
}

rust完整代码

use std::collections::{BinaryHeap, HashMap};

struct Store {
    price_nums: HashMap<i32, i32>,
    heap: BinaryHeap<i32>,
}

impl Store {
    fn new() -> Self {
        Self {
            price_nums: HashMap::new(),
            heap: BinaryHeap::new(),
        }
    }

    fn add(&mut self, num: i32, price: i32) {
        if let Some(count) = self.price_nums.get_mut(&price) {
            *count += num;
        } else {
            self.price_nums.insert(price, num);
            self.heap.push(price);
        }
    }

    fn remove(&mut self, mut num: i32) -> i32 {
        let mut money = 0;
        while !self.heap.is_empty() && num != 0 {
            let price = self.heap.pop().unwrap();
            let stores = *self.price_nums.get(&price).unwrap();

            if num >= stores {
                money += price * stores;
                self.price_nums.remove(&price);
                num -= stores;
            } else {
                money += price * num;
                self.heap.push(price);
                self.price_nums.insert(price, stores - num);
                break;
            }
        }
        money
    }
}

pub struct StoreManager {
    map: HashMap<String, Store>,
}

impl StoreManager {
    pub fn new() -> Self {
        Self {
            map: HashMap::new(),
        }
    }

    pub fn supply(&mut self, item: &str, num: i32, price: i32) {
        let store = self.map.entry(item.to_string()).or_insert(Store::new());
        store.add(num, price);
    }

    pub fn sell(&mut self, item: &str, num: i32) -> i32 {
        self.map.get_mut(item).unwrap().remove(num)
    }
}
fn main() {
    let mut manager = StoreManager::new();

    manager.supply("apple", 10, 3);
    manager.supply("banana", 5, 2);
    manager.supply("orange", 8, 4);

    let total_price = manager.sell("banana", 3);
    println!("Sell 3 bananas: ${}", total_price);

    let total_price = manager.sell("banana", 2);
    println!("Sell 2 bananas: ${}", total_price);

    let total_price = manager.sell("apple", 5);
    println!("Sell 5 apples: ${}", total_price);

    let total_price = manager.sell("orange", 10);
    println!("Sell 10 oranges: ${}", total_price);
}

本作品采用《CC 协议》，转载必须注明作者和本文链接