- void supply(String item, int num, int price)
名字叫item的商品，个数num，价格price。
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);
}
