Uva
本来想用优先队列做，可是不知道怎么处理之间的关系，最后还是用了map方法AC了，不过速度上有些慢，提交的时候跑了1.557秒。估计这道题时间都稍微长些，题目的时间限制也是4.5秒，不像一般题目的3秒限制。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
using namespace std;
struct CMD {
string cmd;
int size, price;
CMD(string kind, int x = 0, int y = 0) :cmd(kind), size(x), price(y) {}
};
map<int, set<int> > BUY, SELL;
map<int, int> BUY_VAL, SELL_VAL;
vector<CMD> D;
void trade(int kind)
{
while (!BUY.empty() && !SELL.empty()) {
if (BUY.rbegin()->first >= SELL.begin()->first) {
set<int> &v1 = BUY.rbegin()->second;
set<int> &v2 = SELL.begin()->second;
int aid = *v1.begin(), bid = *v2.begin();
int z = min(D.size, D.size);
printf("TRADE %d %d\n", z, kind ? D.price : D.price);
D.size -= z, D.size -= z;
BUY_VAL.price] -= z, SELL_VAL.price] -= z;
if (D.size == 0)
v1.erase(aid);
if (D.size == 0)
v2.erase(bid);
if (v1.size() == 0)
BUY.erase(D.price);
if (v2.size() == 0)
SELL.erase(D.price);
}
else {
return;
}
}
}
// 打印QUOTE一行
void print()
{
while (BUY_VAL.size() && BUY_VAL.rbegin()->second == 0) {
BUY_VAL.erase(BUY_VAL.rbegin()->first);
}
while (SELL_VAL.size() && SELL_VAL.begin()->second == 0) {
SELL_VAL.erase(SELL_VAL.begin()->first);
}
printf("QUOTE ");
if (BUY_VAL.size()) {
printf("%d %d", BUY_VAL.rbegin()->second, BUY_VAL.rbegin()->first);
}
else {
printf("0 0");
}
printf(" - ");
if (SELL_VAL.size()) {
printf("%d %d", SELL_VAL.begin()->second, SELL_VAL.begin()->first);
}
else {
printf("0 99999");
}
cout << endl;
}
int main()
{
int Q, cases = 0;
char cmd;
while (scanf("%d", &Q) == 1) {
if (cases++)
{
cout << endl;
}
// 记得清空
BUY.clear(), SELL.clear();
BUY_VAL.clear(), SELL_VAL.clear();
D.clear();
int size, price, id;
// 读入命令并处理交易
for (int i = 0; i < Q; i++) {
scanf("%s", cmd);
if (!strcmp(cmd, "BUY")) {
scanf("%d %d", &size, &price);
BUY.insert(i);
BUY_VAL += size;
D.push_back(CMD("BUY", size, price));
trade(0);
}
else if (!strcmp(cmd, "SELL")) {
scanf("%d %d", &size, &price);
SELL.insert(i);
SELL_VAL += size;
D.push_back(CMD("SELL", size, price));
trade(1);
}
else if (!strcmp(cmd, "CANCEL")) {
scanf("%d", &id), id--;
D.push_back(CMD("CANCEL", id));
if (D.cmd == "BUY") {
BUY.price].erase(id);
if (BUY.price].size() == 0)
BUY.erase(D.price);
BUY_VAL.price] -= D.size;
D.size = 0;
}
if (D.cmd == "SELL") {
SELL.price].erase(id);
if (SELL.price].size() == 0)
SELL.erase(D.price);
SELL_VAL.price] -= D.size;
D.size = 0;
}
}
print();
}
}
return 0;
}
页:
[1]