|
Uva1598
Exchange
设计一个资源交易系统，资源交易系统处理三种请求，分别为买入BUY，卖出SELL和撤销CANCEL。资源交易系统维护当前最高的买入价格bid price和最低的售出价格ask price，当bid price >= ask price时，买卖双方达成交易，规则为：
- 交易量为买卖双方中较少的一方
- 交易价格要满足交易触发方可以获取最大的收益，如果交易是由
BUY请求触发，则交易价格为当前最低的卖出方价格；如果交易是由SELL请求触发，则交易价格为当前最高的买入方价格 - 当一个触发请求可以同多个已有请求达成交易时，根据先来先服务的原则，触发请求依次同已有请求进行交易，直到触发请求的剩余交易量为
0，或者没有满足条件的已有请求，这个过程中可以发生交易价格变化
根据题目中描述的交易规则，交易总是在利润最大的买方和卖方之间完成，所以程序中需要维护一个按照买方价格排序的列表BidPrices和一个按照卖方价格排序的列表AskPrices，然后只需要按照交易规则，从列表中最优的请求开始进行模拟即可。
同时为了支持撤销操作，所有已经到来的请求应该按照先后顺序存放在一个数组orders中，以方便撤销操作的执行。
在输入输出上还需要注意：
- 虽然在无
SELL请求时输出的askprice应该为99999，但是合法的SELL输入包括99999 - 连续的两个测试用例的输入之间没有空行，而连续的两个测试用例的输出之间应该空一行，而最后一个测试用例后不需要多余的空行
#include <iostream>
#include <algorithm>
#include <climits>
#include <list>
#include <map>
#include <string>
#include <vector>
#define MAX_ASK_PRICE 100000
using namespace std;
enum class OrderType
{
BUY, SELL, CANCEL
};
struct Order
{
OrderType type;
int size, price;
bool active;
};
struct OrderQueue
{
int total;
list<size_t> indexes;
OrderQueue() : total(0) {};
void append(int size, size_t index)
{
this->total += size;
indexes.push_back(index);
}
};
void ProcessBuy(vector<Order> &orders, map<int, OrderQueue> &BidPrices, map<int, OrderQueue> &AskPrices)
{
Order &BuyOrder = orders.back();
while (BuyOrder.size != 0 && BuyOrder.price >= AskPrices.begin()->first) {
int AskPrice = AskPrices.begin()->first;
OrderQueue &AskQueue = AskPrices.begin()->second;
while (BuyOrder.size != 0 && !AskQueue.indexes.empty()) {
Order &SellOrder = orders[AskQueue.indexes.front()];
int TradeSize = min(BuyOrder.size, SellOrder.size);
cout << "TRADE " << TradeSize << ' ' << AskPrice << endl;
BuyOrder.size -= TradeSize;
SellOrder.size -= TradeSize;
AskQueue.total -= TradeSize;
if (SellOrder.size == 0) {
SellOrder.active = false;
AskQueue.indexes.pop_front();
}
}
if (AskQueue.indexes.empty()) {
AskPrices.erase(AskPrices.begin());
}
}
BuyOrder.active = BuyOrder.size != 0;
if (BuyOrder.active) {
BidPrices[BuyOrder.price].append(BuyOrder.size, orders.size() - 1);
}
}
void ProcessSell(vector<Order> &orders, map<int, OrderQueue> &BidPrices, map<int, OrderQueue> &AskPrices)
{
Order &SellOrder = orders.back();
while (SellOrder.size != 0 && SellOrder.price <= BidPrices.rbegin()->first) {
int BidPrice = BidPrices.rbegin()->first;
OrderQueue &BidQueue = BidPrices.rbegin()->second;
while (SellOrder.size != 0 && !BidQueue.indexes.empty()) {
Order &BuyOrder = orders[BidQueue.indexes.front()];
int TradeSize = min(SellOrder.size, BuyOrder.size);
cout << "TRADE " << TradeSize << ' ' << BidPrice << endl;
SellOrder.size -= TradeSize;
BuyOrder.size -= TradeSize;
BidQueue.total -= TradeSize;
if (BuyOrder.size == 0) {
BuyOrder.active = false;
BidQueue.indexes.pop_front();
}
}
if (BidQueue.indexes.empty()) {
BidPrices.erase(BidPrices.rbegin()->first);
}
}
SellOrder.active = SellOrder.size != 0;
if (SellOrder.active) {
AskPrices[SellOrder.price].append(SellOrder.size, orders.size() - 1);
}
}
void ProcessCancel(vector<Order> &orders, map<int, OrderQueue> &BidPrices, map<int, OrderQueue> &AskPrices)
{
Order &CanceledOrder = orders[orders.back().size - 1];
if (!CanceledOrder.active) return;
if (CanceledOrder.type == OrderType::BUY) {
OrderQueue &BidQueue = BidPrices[CanceledOrder.price];
BidQueue.total -= CanceledOrder.size;
if (BidQueue.total == 0) {
BidPrices.erase(CanceledOrder.price);
}
else {
BidQueue.indexes.remove_if([&orders](const size_t idx)
{
return idx == orders.back().size - 1;
});
}
}
else {
OrderQueue &AskQueue = AskPrices[CanceledOrder.price];
AskQueue.total -= CanceledOrder.size;
if (AskQueue.total == 0) {
AskPrices.erase(CanceledOrder.price);
}
else {
AskQueue.indexes.remove_if([&orders](const size_t idx)
{
return idx == orders.back().size - 1;
});
}
}
CanceledOrder.active = false;
orders.back().active = false;
}
void PrintQuote(const map<int, OrderQueue> &BidPrices, const map<int, OrderQueue> &AskPrices)
{
cout << "QUOTE ";
cout << BidPrices.rbegin()->second.total << ' ' << BidPrices.rbegin()->first;
cout << " - ";
if (AskPrices.begin()->first == MAX_ASK_PRICE) {
cout << 0 << ' ' << 99999;
}
else {
cout << AskPrices.begin()->second.total << ' ' << AskPrices.begin()->first;
}
cout << endl;
}
int main()
{
bool first = true;
int n = 0;
while (cin >> n) {
if (!first) {
cout << endl;
}
first = false;
vector<Order> orders;
map<int, OrderQueue> BidPrices, AskPrices;
BidPrices[0].append(0, UINT_MAX);
AskPrices[MAX_ASK_PRICE].append(0, UINT_MAX);
for (int i = 0; i < n; i++)
{
string word;
cin >> word;
int size, price, order;
if (word == "BUY") {
cin >> size >> price;
orders.push_back({ OrderType::BUY, size, price, true });
ProcessBuy(orders, BidPrices, AskPrices);
}
else if (word == "SELL") {
cin >> size >> price;
orders.push_back({ OrderType::SELL, size, price, true });
ProcessSell(orders, BidPrices, AskPrices);
}
else if (word == "CANCEL") {
cin >> order;
orders.push_back({ OrderType::CANCEL, order, order, true });
ProcessCancel(orders, BidPrices, AskPrices);
}
PrintQuote(BidPrices, AskPrices);
}
}
return 0;
}
|