最牛论坛网站,app生成链接,国内最好的危机公关公司,汽车网站你的任务是为交易所设计一个订单处理系统。要求支持以下3种指令。 BUY p q#xff1a;有人想买#xff0c;数量为p#xff0c;价格为q。 SELL p q#xff1a;有人想卖#xff0c;数量为p#xff0c;价格为q。 CANCEL i#xff1a;取消第i条指令对应的订单#xff08;输…你的任务是为交易所设计一个订单处理系统。要求支持以下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) - Optionstd::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) - Optionstd::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: VecOrder vec![];let mut buy_list: BinaryHeapBuy BinaryHeap::new();let mut sell_list: BinaryHeapSell 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: Vecbool 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: Vecusize 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 BinaryHeapBuy,sell_list: mut BinaryHeapSell,buy_amount_price: mut HashMapusize, usize,sell_amount_price: mut HashMapusize, usize,orders: mut VecOrder,bvalid: Vecbool,
) {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();}
}
