习题5-14 交易所（Exchange，ACM/ICPC NEERC 2006，UVa1598）

本文主要是介绍习题5-14 交易所（Exchange，ACM/ICPC NEERC 2006，UVa1598），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-1598
分类：STL综合
备注：复杂模拟,阅读理解
前言：在别处找到一篇很nice的翻译：https://blog.csdn.net/zju2016/article/details/75005098?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
顺便他还有题解，但是我搞不懂map的迭代器的用法，比如map.rbegin是指向哪里(我知道是begin的前面,但是不知道元素应该是什么)，map元素的顺序是什么样的，我没弄懂，目前也没查到，就没抄他的。但是因为他的代码我知道这题必须要erase(在此之前我已经TLE很多次了!)，当题目开始注重效率难度就上升了一小层啊…

代码如下：

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn = 1e4 + 5;
const int inf = 99999;
int bnum, bpri, snum, spri;struct COrder {string type;int num, pri, act = 1;
}ord[maxn];set<int, greater<int> >buy;//记录buy的pri
set<int, less<int> >sell;//记录sell的pri
map<int, set<int> >buyxb;//记录同种pri的buy订单的下标
map<int, set<int> >sellxb;//记录同种pri的sell订单的下标
map<int, int>buy_tot;//buy价格映射总数
map<int, int>sell_tot;//sell价格映射总数void trade(int xb, string x, int pri){if (x[0] == 'B') {if (pri < spri)return;for (set<int, less<int> >::iterator it = sell.begin(); it != sell.end();) {if (!ord[xb].act) break;for (set<int>::iterator it2 = sellxb[*it].begin(); it2 != sellxb[*it].end(); ++it2) {if (!ord[*it2].act)continue;if (ord[*it2].pri <= pri) {int ntmp = min(ord[xb].num, ord[*it2].num);ord[*it2].num -= ntmp; sell_tot[*it] -= ntmp;if (!ord[*it2].num)ord[*it2].act = 0;ord[xb].num -= ntmp; buy_tot[pri] -= ntmp;printf("TRADE %d %d\n", ntmp, ord[*it2].pri);if (!ord[xb].num) { ord[xb].act = 0; break; }}}if (!sell_tot[*it]) sell.erase(it++);else it++;}}else {if (pri > bpri)return;for (set<int,greater<int> >::iterator it = buy.begin(); it != buy.end(); ) {if (!ord[xb].act) break;for (set<int>::iterator it2 = buyxb[*it].begin(); it2 != buyxb[*it].end(); ++it2) {if (!ord[*it2].act)continue;if (ord[*it2].pri >= pri) {int ntmp = min(ord[xb].num, ord[*it2].num);ord[*it2].num -= ntmp; buy_tot[*it] -= ntmp;if (!ord[*it2].num)ord[*it2].act = 0;ord[xb].num -= ntmp; sell_tot[pri] -= ntmp;printf("TRADE %d %d\n", ntmp, ord[*it2].pri);if (!ord[xb].num) { ord[xb].act = 0; break; }}}if (!buy_tot[*it]) buy.erase(it++);else it++;}}
}void output(){bnum = buy_tot.count(bpri) ? buy_tot[bpri] : 0, snum = sell_tot[spri], sell_tot.count(spri) ? sell_tot[spri] : 0;if (!bnum) {bpri = 0;for (set<int,greater<int> >::iterator it = buy.begin(); it != buy.end(); ++it) {if (buy_tot[*it]) {bpri = *it; bnum = buy_tot[*it]; break;}}}if (!snum) {spri = inf;for (set<int,less<int> >::iterator it = sell.begin(); it != sell.end(); ++it) {if (sell_tot[*it]) {spri = *it; snum = sell_tot[*it]; break;}}}printf("QUOTE %d %d - %d %d\n", bnum, bpri, snum, spri);
}int main(void) {int n, flag = 0;while (~scanf("%d", &n)) {buy.clear(); sell.clear();buyxb.clear(); sellxb.clear();buy_tot.clear(); sell_tot.clear();if (flag)printf("\n");else flag = 1;bnum = 0, bpri = 0, snum = 0, spri = inf;string s;for (int i = 1; i <= n; i++) {cin >> s;if (s[0] == 'C') {int xb;scanf("%d", &xb);if (ord[xb].act) {ord[xb].act = 0;if (ord[xb].type[0] == 'B') {buy_tot[ord[xb].pri] -= ord[xb].num;if (!buy_tot[ord[xb].pri]) {set<int, greater<int> >::iterator it = buy.find(ord[xb].pri);if (it != buy.end())buy.erase(it);}}else {sell_tot[ord[xb].pri] -= ord[xb].num;if (!sell_tot[ord[xb].pri]) {set<int, greater<int> >::iterator it = sell.find(ord[xb].pri);if (it != sell.end())sell.erase(it);}}}}else{int num, pri; scanf("%d%d", &num, &pri);ord[i].type = s, ord[i].num = num, ord[i].pri = pri, ord[i].act = 1;if (s[0] == 'B') {buy.insert(pri); buyxb[pri].insert(i); buy_tot[pri] += num;if (pri > bpri) bpri = pri;}else {sell.insert(pri); sellxb[pri].insert(i); sell_tot[pri] += num;if (pri < spri)spri = pri;}trade(i, s, pri);}output();}}return 0;
}