0%

算法竞赛入门经典(第2版) 5-14UVa1598 - Exchange

题意:模拟买卖,当出售价bid等于或低于出售价ask,则交易。


代码:(Accepted,0.330s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//UVa1598 - Exchange
//Accepted 0.330s
//#define _XIENAOBAN_
#include<functional>
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;

struct INFO { char type; int size, price; }for_push_back;
int N, T(0);
char type[20];
vector<INFO> LIST; //key: buy/ask id, value: type, size
map<int, set<int>, greater<int> > BUY; //key: bid price, value: id
map<int, set<int>, less<int> > SELL; //key: ask price, value: id
map<int, int> BUY_VAL; //key: bid price, value: size
map<int, int> SELL_VAL; //key: ask price, value: size

inline int sum(set<int>& now) {
int re(0);
for (const auto& r : now) re += LIST[r].size;
return re;
}

void trade(bool flag) {
int bid_size, bid_price, ask_size, ask_price;
while (true) {
auto bid(BUY.begin()), ask(SELL.begin());
if (bid == BUY.end()) bid_size = 0, bid_price = 0;
else bid_size = BUY_VAL[bid->first], bid_price = bid->first;
if (ask == SELL.end()) ask_size = 0, ask_price = 999999;
else ask_size = SELL_VAL[ask->first], ask_price = ask->first;
if (bid_price < ask_price) {
printf("QUOTE %d %d - %d %d\n", bid_size, bid_price, ask_size, (ask_price == 999999 ? 99999 : ask_price));
return;
}
auto sizeb(LIST[*bid->second.begin()].size), sizea(LIST[*ask->second.begin()].size);
const auto mini(min(sizeb, sizea));
printf("TRADE %d %d\n", mini, flag ? ask_price : bid_price);

auto& b(bid->second), &a(ask->second);
BUY_VAL[bid->first] -= mini;
if (!b.empty() && (LIST[*b.begin()].size -= mini) == 0)
b.erase(b.begin());
if (b.empty()) BUY.erase(bid);
SELL_VAL[ask->first] -= mini;
if (!a.empty() && (LIST[*a.begin()].size -= mini) == 0)
a.erase(a.begin());
if (a.empty()) SELL.erase(ask);
}
}

int main()
{
#ifdef _XIENAOBAN_
#define gets(T) gets_s(T, 66666)
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

while (scanf("%d", &N) != EOF) {
if (T++) puts("");
LIST.clear(), BUY.clear(), SELL.clear(), BUY_VAL.clear(), SELL_VAL.clear();
LIST.push_back(for_push_back);
for (int n(1);n <= N;++n) {
INFO tmp;
scanf("%s", type);
if (*type == 'C') {
int id;
scanf("%d", &id);
auto& csl(LIST[id]);
if (csl.type == 'B') {
BUY_VAL[csl.price] -= csl.size;
LIST[id].size = 0;
auto& now(BUY[csl.price]);
now.erase(id);
if (now.empty()) BUY.erase(csl.price);
}
else {
SELL_VAL[csl.price] -= csl.size;
LIST[id].size = 0;
auto& now(SELL[csl.price]);
now.erase(id);
if (now.empty()) SELL.erase(csl.price);
}
}
else {
tmp.type = *type;
scanf("%d%d", &tmp.size, &tmp.price);
if (*type == 'B') BUY[tmp.price].insert(n), BUY_VAL[tmp.price] += tmp.size;
else SELL[tmp.price].insert(n), SELL_VAL[tmp.price] += tmp.size;
}
LIST.push_back(std::move(tmp));
trade(*type == 'B');
}
}
return 0;
}

分析:书上推荐使用优先队列,然而并没有想出来怎么去用。想了想还是用了map,用它的begin(),效果一样的,还可以灵活差入数据。一开始老是在某组测试数据上出现Runtime error,搞得生无可恋。(从一老司机学到的新技能:当提交OJ出现RE时(WA也行),在执行每组数据计算的代码末尾加一句“while(1);”再提交如果从RE变成TLE了则说明是某些特殊数据没照顾到。毕竟不是所有OJ都有udebug可以用,这招还是不错的) 然后过了一天还是心里放不下,又回来想了想,是题目中一个细节“If there is no active order to sell, then it is assumed that ask size is zero and ask price is 99 999. Note, that zero is not a legal price, but 99 999 is a legal price. Recipient of quote messages distinguishes actual 99 999 ask price from the special case of absent orders to sell by looking at its ask size.”出了问题。于是把不可交易价格改成999999,与交易最大价格加以99999区分,果然似乎没问题了。然而接下来就有新问题,Time limit exceeded。。。 又过了一天,心里还是放不下,于是去网上查了查别人的代码,他们不仅用两个map存买卖信息,还再单独开辟两个map来存放sell与buy的总size(就相当于我上面那两个BUY_VALSELL_VAL),而当时我只用了两个map(BUYSELL)存买卖的所有信息,所以每次查询循环总的size时要经历一个比较烦的循环,就是以下这个循环:

1
2
3
4
5
6
//求当前价格总的size函数
int sum(set<int>& now) {
int re(0);
for (const auto& r : now) re += LIST[r].size;
return re;
}
1
2
3
4
5
6
//trade函数片段
auto bid(BUY.begin()), ask(SELL.begin());
if (bid == BUY.end()) bid_size = 0, bid_price = 0;
else bid_size = sum(bid->second), bid_price = bid->first;
if (ask == SELL.end()) ask_size = 0, ask_price = 999999;
else ask_size = sum(ask->second), ask_price = ask->first;

这就是超时的罪魁祸首。改进了下瞬间变成0.330s,还是有些出乎意料。