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

你的任务是为交易所设计一个订单处理系统。要求支持以下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

分析：
一个订单成交过的部分不能取消。

解法：

use std::{collections::{BinaryHeap, HashMap},io::{self, Read},
};
struct Order {_id: usize,amount: usize,price: usize,op: String,
}
#[derive(Debug, PartialEq, Eq)]
struct Buy {id: usize,amount: usize,price: usize,
}
impl Ord for Buy {fn cmp(&self, other: &Self) -> std::cmp::Ordering {if self.price != other.price {self.price.cmp(&other.price)} else {other.id.cmp(&self.id)}}
}
impl PartialOrd for Buy {fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {Some(self.cmp(other))}
}
#[derive(Debug, PartialEq, Eq)]
struct Sell {id: usize,amount: usize,price: usize,
}
impl Ord for Sell {fn cmp(&self, other: &Self) -> std::cmp::Ordering {if self.price != other.price {other.price.cmp(&self.price)} else {other.id.cmp(&self.id)}}
}
impl PartialOrd for Sell {fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {Some(self.cmp(other))}
}
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: BinaryHeap<Buy> = BinaryHeap::new();let mut sell_list: BinaryHeap<Sell> = BinaryHeap::new();let mut buy_amount_price = HashMap::new();let mut sell_amount_price = HashMap::new();buy_list.push(Buy {id: usize::MAX,amount: 0,price: 0,});sell_list.push(Sell {id: usize::MAX,amount: 0,price: 99999,});buy_amount_price.insert(0, 0);sell_amount_price.insert(99999, 0);let mut bvalid: Vec<bool> = vec![true; n];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 {_id: i,amount: 0,price: 0,op: cmd.to_string(),});let cancel_id = v[0] - 1;let aorder = &orders[cancel_id];if aorder.op == "BUY" && bvalid[cancel_id] {if let Some(x) = buy_amount_price.get_mut(&aorder.price) {*x -= aorder.amount;}} else if aorder.op == "SELL" && bvalid[cancel_id] {sell_amount_price.entry(aorder.price).and_modify(|x| *x -= aorder.amount);}bvalid[cancel_id] = false;} 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.push(Buy { id, amount, price });buy_amount_price.entry(price).and_modify(|x| *x += amount).or_insert(amount);} else {sell_list.push(Sell { id, amount, price });sell_amount_price.entry(price).and_modify(|x| *x += amount).or_insert(amount);}let a = Order {_id: id,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,&bvalid,);let price = buy_list.peek().unwrap().price;print!("QUOTE {} {}", buy_amount_price.get(&price).unwrap(), price);let price = sell_list.peek().unwrap().price;print!(" - {} {}", sell_amount_price.get(&price).unwrap(), price);println!();}
}fn trade(op: &String,buy_list: &mut BinaryHeap<Buy>,sell_list: &mut BinaryHeap<Sell>,buy_amount_price: &mut HashMap<usize, usize>,sell_amount_price: &mut HashMap<usize, usize>,orders: &mut Vec<Order>,bvalid: &Vec<bool>,
) {while buy_list.len() > 1 && sell_list.len() > 1 {let buy = buy_list.peek().unwrap();let sell = sell_list.peek().unwrap();if buy.price < sell.price {break;}if !bvalid[buy.id] {buy_list.pop();continue;}if !bvalid[sell.id] {sell_list.pop();continue;}let mut buy = buy_list.pop().unwrap();let mut sell = sell_list.pop().unwrap();let min_amount = buy.amount.min(sell.amount);orders[buy.id].amount -= min_amount;orders[sell.id].amount -= min_amount;buy.amount -= min_amount;sell.amount -= min_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);if op == "BUY" {println!("TRADE {} {}", min_amount, sell.price);} else if op == "SELL" {println!("TRADE {} {}", min_amount, buy.price);}if buy.amount > 0 {buy_list.push(buy);}if sell.amount > 0 {sell_list.push(sell);}}//如果队首是被取消的订单while buy_list.len() > 1 {let buy = buy_list.peek().unwrap();if bvalid[buy.id] {break;}buy_list.pop();}while sell_list.len() > 1 {let sell = sell_list.peek().unwrap();if bvalid[sell.id] {break;}sell_list.pop();}
}