商品交易市场系统解析

这个问题模拟了一个商品交易市场的运作机制，要求我们处理买入和卖出订单，并生成相应的交易报告。系统需要匹配符合条件的订单，并按规则生成交易价格，最后输出商品和交易者的统计信息。

核心数据结构与设计思路

1. 订单存储：

   • 使用三维数组q[2][26]存储未成交订单，其中：
     • 第一维：0表示买入订单，1表示卖出订单
     • 第二维：26个字母表示不同商品
     • 每个元素是一个pair<string, int>，存储交易者姓名和报价

2. 交易记录：

   • com_output[26]：存储每个商品的交易价格
   • deal_output：存储每个交易者的支付和收入金额

3. 订单匹配策略：

   • 卖出订单：寻找最高价的买入订单（相同价格选最早的）
   • 买入订单：寻找最低价的卖出订单（相同价格选最早的）

核心算法解析

1. 订单处理流程：

   • 读取订单信息，确定商品和订单类型
   • 查找是否有匹配的订单：
     • 卖出订单：查找价格最高且大于等于当前报价的买入订单
     • 买入订单：查找价格最低且小于等于当前报价的卖出订单
   • 若找到匹配订单：
     • 计算交易价格（平均向下取整）
     • 更新交易记录
     • 移除已成交的订单
   • 若未找到匹配订单：
     • 将当前订单加入未成交列表

2. 结果输出：

   • 商品信息：按字母顺序输出每个商品的最低、平均、最高交易价格
   • 交易者信息：按字典序输出每个交易者的支付和收入金额

代码实现

#include <iostream>
#include <vector>
#include <set>
#include <limits>
#include <map>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
  int N;
  while (cin >> N && N != 0) {
    vector<pair<string,int> > q[2][26];
    vector<int> com_output[26];
    map<string, pair<int,int> > deal_output;
    for (int i = 0; i < N; i++) {
      string name, action;
      char com;
      int price;
      cin >> name >> action >> com >> price;
      const int c = com - 'A';
      const bool b = action == "SELL";
      if (!deal_output.count(name)) {
        deal_output[name] = make_pair(0, 0);
      }
      vector<pair<string,int> >::iterator it = q[b][c].end();
      if (b) {
        for (vector<pair<string,int> >::iterator jt(q[b][c].begin()); jt != q[b][c].end(); ++jt) {
          if (jt->first != name && jt->second >= price
              && (it == q[b][c].end() || it->second < jt->second)) {
            it = jt;
          }
        }
      } else {
        for (vector<pair<string,int> >::iterator jt(q[b][c].begin()); jt != q[b][c].end(); ++jt) {
          if (jt->first != name && jt->second <= price
              && (it == q[b][c].end() || it->second > jt->second)) {
            it = jt;
          }
        }
      }
      if (it == q[b][c].end()) {
        q[!b][c].push_back(make_pair(name, price));
      } else {
        const int p = (price + it->second) / 2;
        com_output[c].push_back(p);
        deal_output[b ? name : it->first].second += p;
        deal_output[b ? it->first : name].first += p;
        q[b][c].erase(it);
      }
    }
    for (int c = 0; c < 26; c++) {
      if (!com_output[c].empty()) {
        const vector<int>& v = com_output[c];
        int lowest = v[0], highest = v[0], sum = 0;
        for (vector<int>::const_iterator it(v.begin()); it != v.end(); ++it) {
          lowest = min(lowest, *it);
          highest = max(highest, *it);
          sum += *it;
        }
        cout << char('A'+c) << ' ' << lowest << ' ' << sum/v.size() << ' ' << highest << endl;
      }
    }
    cout << "--" << endl;
    for (map<string, pair<int,int> >::const_iterator it(deal_output.begin()); it != deal_output.end(); ++it) {
      cout << it->first << ' ' << it->second.first << ' ' << it->second.second << endl;
    }
    cout << "----------" << endl;
  }
  return 0;
}

注意事项

1. 订单匹配规则：

   • 必须排除同一交易者的订单
   • 价格优先，时间优先（遍历顺序保证）

2. 数据结构选择：

   • 使用vector存储订单，确保按时间顺序处理
   • 使用map存储交易者信息，自动按字典序排序

3. 输出格式：

   • 商品按字母顺序输出
   • 交易者按字典序输出
   • 注意分隔线和空行的格式