UVA-1598 交易所 题解答案代码 算法竞赛入门经典第二版

​​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;
}