当前位置：首页 > news >正文

交易所（Exchange, ACM/ICPC NEERC 2006, UVa1598）rust解法

news 来源：原创 2024/5/9 19:51:02

你的任务是为交易所设计一个订单处理系统。要求支持以下3种指令。
BUY p q：有人想买，数量为p，价格为q。
SELL p q：有人想卖，数量为p，价格为q。
CANCEL i：取消第i条指令对应的订单（输入保证该指令是BUY或者SELL）。
交易规则如下：对于当前买订单，若当前最低卖价低于当前出价，则发生交易；对于当前卖订单，若当前最高买价高于当前价格，则发生交易。发生交易时，按供需物品个数的最小值交易。交易后，需修改订单的供需物品个数。当出价或价格相同时，按订单产生的先后顺序发生交易。

样例：
输入

11
BUY 100 35
CANCEL 1
BUY 100 34
SELL 150 36
SELL 300 37
SELL 100 36
BUY 100 38
CANCEL 4
CANCEL 7
BUY 200 32
SELL 500 30

输出

QUOTE 100 35 - 0 99999
QUOTE 0 0 - 0 99999
QUOTE 100 34 - 0 99999
QUOTE 100 34 - 150 36
QUOTE 100 34 - 150 36
QUOTE 100 34 - 250 36
TRADE 100 36
QUOTE 100 34 - 150 36
QUOTE 100 34 - 100 36
QUOTE 100 34 - 100 36
QUOTE 100 34 - 100 36
TRADE 100 34
TRADE 200 32
QUOTE 0 0 - 200 30

分析：
一个订单成交过的部分不能取消。只能取消剩余的部分。比如SELL 150 36，已经成交了100个，还剩余50个，所以当取消这个订单时，只能取消那50个。

解法：

use std::{collections::{BTreeMap, BTreeSet, HashMap},io::{self, Read},
};
struct Order {amount: usize,price: usize,op: String,
}fn main() {let mut buf = String::new();io::stdin().read_line(&mut buf).unwrap();let n: usize = buf.trim().parse().unwrap();let mut orders: Vec<Order> = vec![]; //所有订单let mut buy_list: BTreeMap<usize, BTreeSet<usize>> = BTreeMap::new(); // 买价对应的订单idlet mut sell_list: BTreeMap<usize, BTreeSet<usize>> = BTreeMap::new(); //卖价对应的订单idlet mut buy_amount_price = HashMap::new(); //买价对应的总数量let mut sell_amount_price = HashMap::new(); //卖价对应的总数量let mut buf = String::new();io::stdin().read_to_string(&mut buf).unwrap();let mut lines = buf.lines();for i in 0..n {let mut it = lines.next().unwrap().split_whitespace();let cmd = it.next().unwrap();let v: Vec<usize> = it.map(|x| x.parse().unwrap()).collect();if cmd == "CANCEL" {orders.push(Order {amount: 0,price: 0,op: cmd.to_string(),});let cancel_id = v[0] - 1;let aorder = &mut orders[cancel_id];if aorder.op == "BUY" {sell_amount_price.entry(aorder.price).and_modify(|x| *x -= aorder.amount);aorder.amount = 0;if let Some(v) = buy_list.get_mut(&aorder.price) {v.remove(&cancel_id);if v.is_empty() {buy_list.remove(&aorder.price);}}} else if aorder.op == "SELL" {sell_amount_price.entry(aorder.price).and_modify(|x| *x -= aorder.amount);aorder.amount = 0;if let Some(v) = sell_list.get_mut(&aorder.price) {v.remove(&cancel_id);if v.is_empty() {sell_list.remove(&aorder.price);}}}} else if cmd == "BUY" || cmd == "SELL" {let id = i;let amount = v[0];let price = v[1];let op = cmd.to_string();if cmd == "BUY" {buy_list.entry(price).and_modify(|x| {x.insert(id);}).or_insert(BTreeSet::from([id]));buy_amount_price.entry(price).and_modify(|x| *x += amount).or_insert(amount);} else {sell_list.entry(price).and_modify(|x| {x.insert(id);}).or_insert(BTreeSet::from([id]));sell_amount_price.entry(price).and_modify(|x| *x += amount).or_insert(amount);}let a = Order { amount, price, op };orders.push(a);}trade(&cmd.to_string(),&mut buy_list,&mut sell_list,&mut buy_amount_price,&mut sell_amount_price,&mut orders,);if let Some(x) = buy_list.last_entry() {let price = x.key();print!("QUOTE {} {}", buy_amount_price.get(&price).unwrap(), price);} else {print!("QUOTE 0 0");}if let Some(x) = sell_list.first_entry() {let price = x.key();print!(" - {} {}", sell_amount_price.get(&price).unwrap(), price);} else {print!(" - 0 99999");}println!();}
}fn trade(op: &String,buy_list: &mut BTreeMap<usize, BTreeSet<usize>>,sell_list: &mut BTreeMap<usize, BTreeSet<usize>>,buy_amount_price: &mut HashMap<usize, usize>,sell_amount_price: &mut HashMap<usize, usize>,orders: &mut Vec<Order>,
) {loop {if buy_list.is_empty() || sell_list.is_empty() {break;}let mut buy_entry = buy_list.last_entry().unwrap(); //因为map是升序，而我们要取最大买价，所以每次取最后一个元素let mut sell_entry = sell_list.first_entry().unwrap(); //因为map是升序，取最小卖价，每次取第一个元素let buy_price = *buy_entry.key();let sell_price = *sell_entry.key();if buy_price < sell_price {break;}let buy_ids = buy_entry.get_mut();let buyid = buy_ids.pop_first().unwrap();let sell_ids = sell_entry.get_mut();let sellid = sell_ids.pop_first().unwrap();let min_amount = orders[buyid].amount.min(orders[sellid].amount);buy_amount_price.entry(buy_price).and_modify(|x| *x -= min_amount);sell_amount_price.entry(sell_price).and_modify(|x| *x -= min_amount);orders[buyid].amount -= min_amount;orders[sellid].amount -= min_amount;if orders[buyid].amount > 0 {buy_ids.insert(buyid);} else if buy_ids.is_empty() {buy_list.remove(&buy_price);}if orders[sellid].amount > 0 {sell_ids.insert(sellid);} else if sell_ids.is_empty() {sell_list.remove(&sell_price);}if op == "BUY" {println!("TRADE {} {}", min_amount, sell_price);} else if op == "SELL" {println!("TRADE {} {}", min_amount, buy_price);}}
}