GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

AC代码

有意思的一个题目。书上说这是一个不错的优先队列练习题，但实际上它其实是一个让我们了解优先队列有哪些限制的题目。

其他同学的很多题解因为优先队列限制太大，转而使用了map等结构作为优先队列的代替。我这里还是使用的优先队列。

这个题目碰到的优先队列的限制有：

1. 不能清空优先队列，无法clear

2. 不能遍历，只能查看堆顶元素

3. 默认是大顶堆，自行改变判断规则有些麻烦

因此，如果想要用优先队列做这道题，必须用到很多辅助的数据结构，比如我用到了vector,map来辅助查找。不能清空，那就只能重新赋值空队列了。

这个题目的一些注意事项：

1. 题目可能有多组数据，每组之间需要空行

2. 成交价格对当前处理的最新消息有利。比如如果新来的是买消息，那么买的价格会按照当前卖出队列的最低价格成交，而不是买消息中的价格。卖消息则使用买入队列的最高价格成交。

（所以如果我是参与交易者，我会一直出价再撤回，这样才有可能以最低价格买入，最高价格卖出）

3. 撤回消息时，如果该消息已经交易成功，那么无需任何处理。如果未成功或者已经成功了一部分，则剩下的部分被禁止交易。输出的最低最高价格中也不包含撤回的消息。

4. 如果新来的一个消息与多个队列中的消息成交，且价格相同，那么在成交的消息中，不需要合并为一条消息输出，而是分成多条输出。比如。

TRADE 200 32

TRADE 200 32

TRADE 300 32

但是在QUOTE消息中，同价格的却需要合并到一条输出。

#include<iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;

struct MES {
	int id;
	int size;
	int price;
	int bs;
	bool operator< (const MES &rhs) const {
		if(this->price != rhs.price) {
			return this->price < rhs.price;
		}
		return this->id > rhs.id;
	}
	bool operator> (const MES &rhs) const {
		if(this->price != rhs.price) {
			return this->price > rhs.price;
		}
		return this->id > rhs.id;
	}
};

vector<MES> vmes;
priority_queue<MES, vector<MES>, less<MES>> buys;
priority_queue<MES, vector<MES>, greater<MES>> sells;
map<int, int> mpBuy, mpSell;

void deleteMes(int id) {
	if(id >= vmes.size() || !vmes[id].size) {
		return;
	}
	if(vmes[id].bs > 0) {
		mpBuy[vmes[id].price] -= vmes[id].size;
	} else {
		mpSell[vmes[id].price] -= vmes[id].size;
	}
	vmes[id].size = 0;
}

void buyMes(MES &m) {
	MES m1, m2;
	int size, price;
	while(!sells.empty() && m.size) {
		m1 = sells.top();
		if(vmes[m1.id].size == 0) {
			sells.pop();
			continue; 
		}
		if(vmes[m1.id].price > m.price) {
			break;
		}
		price = vmes[m1.id].price;
		if(m.size >= vmes[m1.id].size) {
			size = vmes[m1.id].size;
			sells.pop();
		} else {
			size = m.size;
		}
		mpSell[price] -= size;
		m.size -= size;
		vmes[m1.id].size -= size;
		cout << "TRADE " << size << " " << price << endl;
	}
}

void sellMes(MES &m) {
	MES m1, m2;
	int size, price;
	while(!buys.empty() && m.size) {
		m1 = buys.top();
		if(vmes[m1.id].size == 0) {
			buys.pop();
			continue; 
		}
		if(vmes[m1.id].price < m.price) {
			break;
		}
		price = vmes[m1.id].price;
		if(m.size >= vmes[m1.id].size) {
			size = vmes[m1.id].size;
			buys.pop();
		} else {
			size = m.size;
		}
		mpBuy[price] -= size;
		m.size -= size;
		vmes[m1.id].size -= size;
		cout << "TRADE " << size << " " << price << endl;
	}
}

int main() {
	int n, i, j, k;
	int id;
	string s;
	MES m1, m2;
	int size, price;
	bool flag = false; 
	while(cin >> n && n != 0) {
		if(flag == false) {
			flag = true;
		} else {
			cout << endl; 
		}
		priority_queue<MES, vector<MES>, less<MES>> buysT;
		priority_queue<MES, vector<MES>, greater<MES>> sellsT;
		buys = buysT;
		sells = sellsT;
		mpBuy.clear();
		mpSell.clear();
		vmes.clear();
		for(i = 0; i < n; ++i) {
			MES m;
			m.id = i;
			cin >> s;
			if(s == "CANCEL") {
				cin >> id;
				id = id - 1;
				deleteMes(id);
				m.price = 0;
				m.size = 0;
			} else {
				cin >> m.size >> m.price;
				if (s == "BUY") {
					m.bs = 1;
					buyMes(m);
					if(m.size > 0) {
						if(!mpBuy.count(m.price)) {
							mpBuy[m.price] = 0;
						}
						mpBuy[m.price] += m.size;
						buys.push(m);
					}
				} else { //sell
					m.bs = -1;
					sellMes(m);
					if(m.size > 0) {
						if(!mpSell.count(m.price)) {
							mpSell[m.price] = 0;
						}
						mpSell[m.price] += m.size;
						sells.push(m);
					}
				}
			}
			vmes.push_back(m);
			cout << "QUOTE ";
			size = 0; price = 0;
			while(!buys.empty()) {
				m1 = buys.top();
				if(vmes[m1.id].size == 0) {
					buys.pop();
					continue; 
				}
				price = vmes[m1.id].price;
				size =  mpBuy[vmes[m1.id].price];
				break; 
			}
			cout << size << " " << price;
			cout << " - ";
			size = 0; price = 99999;
			while(!sells.empty()) {
				m1 = sells.top();
				if(vmes[m1.id].size == 0) {
					sells.pop();
					continue; 
				}
				price = vmes[m1.id].price;
				size =  mpSell[vmes[m1.id].price];
				break;
			}
			cout << size << " " << price;
			cout << endl; 
		}
	}
	return 0;
}