POJ 1407 - e-Market

http://poj.org/problem?id=1407

概要

マーケットの注文リストが与えられるので，実際に行われる取引の結果を出力する．

注文は sell と buy の2種類があり，どちらも注文を出した人の名前と品物の名前と値段から成る． sell の値段が buy の値段以下のときに限り，sell の値段と buy の値段の平均(切り捨て)の値段で取引が行われる． ただし同じ人物からの sell の注文と buy の注文の間では取引は成立しない．

マーケットの注文リストは注文が出された順に並んでおり，

• 新しく sell の注文がきたときは，buy の注文の中から最も高い値段のものと取引が成立する．もしそのような注文が複数あったら，最も早く注文されたものと取引が成立する．
• 新しく buy の注文がきたときは，sell の注文の中から最も低い値段のものと取引が成立する．もしそのような注文が複数あったら，最も早く注文されたものと取引が成立する．

という規則に従って取引が行われる．

このとき，各商品について商品名の辞書順に

• 最低の値段
• 値段の平均(切り捨て)
• 最高の値段

を出力し，また各参加者について名前の辞書順に

• 払った金額の合計
• 受け取った金額の合計

も出力する．

制約

• 注文の数は 1000 未満
• 人の名前は大文字のアルファベットのみから成り10字以下
• 商品の名前は大文字のアルファベット1文字
• 値段は 1000 未満

解法

言われた通りに実装．重いわけではないが面倒．

 1 #include <iostream>
 2 #include <vector>
 3 #include <set>
 4 #include <limits>
 5 #include <map>
 6 #include <algorithm>
 7 #include <functional>
 8 using namespace std;
 9 
10 int main()
11 {
12   int N;
13   while (cin >> N && N != 0) {
14     vector<pair<string,int> > q[2][26];
15     vector<int> com_output[26];
16     map<string, pair<int,int> > deal_output;
17     for (int i = 0; i < N; i++) {
18       string name, action;
19       char com;
20       int price;
21       cin >> name >> action >> com >> price;
22       const int c = com - 'A';
23       const bool b = action == "SELL";
24       if (!deal_output.count(name)) {
25         deal_output[name] = make_pair(0, 0);
26       }
27       vector<pair<string,int> >::iterator it = q[b][c].end();
28       if (b) {
29         for (vector<pair<string,int> >::iterator jt(q[b][c].begin()); jt != q[b][c].end(); ++jt) {
30           if (jt->first != name && jt->second >= price
31               && (it == q[b][c].end() || it->second < jt->second)) {
32             it = jt;
33           }
34         }
35       } else {
36         for (vector<pair<string,int> >::iterator jt(q[b][c].begin()); jt != q[b][c].end(); ++jt) {
37           if (jt->first != name && jt->second <= price
38               && (it == q[b][c].end() || it->second > jt->second)) {
39             it = jt;
40           }
41         }
42       }
43       if (it == q[b][c].end()) {
44         q[!b][c].push_back(make_pair(name, price));
45       } else {
46         const int p = (price + it->second) / 2;
47         com_output[c].push_back(p);
48         deal_output[b ? name : it->first].second += p;
49         deal_output[b ? it->first : name].first += p;
50         q[b][c].erase(it);
51       }
52     }
53     for (int c = 0; c < 26; c++) {
54       if (!com_output[c].empty()) {
55         const vector<int>& v = com_output[c];
56         int lowest = v[0], highest = v[0], sum = 0;
57         for (vector<int>::const_iterator it(v.begin()); it != v.end(); ++it) {
58           lowest = min(lowest, *it);
59           highest = max(highest, *it);
60           sum += *it;
61         }
62         cout << char('A'+c) << ' ' << lowest << ' ' << sum/v.size() << ' ' << highest << endl;
63       }
64     }
65     cout << "--" << endl;
66     for (map<string, pair<int,int> >::const_iterator it(deal_output.begin()); it != deal_output.end(); ++it) {
67       cout << it->first << ' ' << it->second.first << ' ' << it->second.second << endl;
68     }
69     cout << "----------" << endl;
70   }
71   return 0;
72 }