AOJ 1225 : e-market
問題リンク : e-market | Aizu Online Judge
問題概要:
マーケットの情報が次の形式で与えられる(与えられる情報は1000未満)
ディーラーの名前 オーダー(sell か buyか)商品名 金額
情報が与えられた順番でオーダーされたものとする
つまり、最初に与えられた情報が一番最初にマーケットにでた(最も古い)オーダーである
取引は次のルールにしたがって行われる
・SELLの場合、今マーケットにでているBUYの中でSELLの価格以上の中で最も高い価格を出すディーラーと取引をする
最大の価格を出すディーラーが複数存在する場合は最も古いオーダーのディーラーと取引する
・BUYの場合、今マーケットにでている(今与えられた情報以前で与えられた)SELLの中でBUYの価格以下の中で最も安い価格で売っているディーラーと取引する
BUYの価格以下で最安値のディーラーが複数存在する場合は最も古いオーダーのディーラーと取引をする
一度取引した商品を2回以上取引することはできない
これらの情報を元に、各商品の取引価格の最小、平均、最大と
各ディーラーがこの取引で払った金額、受け取った金額を出力せよ
平均は小数点以下を切り捨てること
出力時に商品名とディーラーは辞書順にすること
解法:
そのとおりに書く
構造体をつかって書くと楽になるかもしれない
コード:
#include<iostream> #include<algorithm> #include<map> #include<cmath> #include<vector> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define inf (1<<29) #define all(n) (n).begin(),(n).end() using namespace std; typedef pair<int,int> ii;//first -> paid, received struct P { int low,avg,hig,total,cnt; P(int low=inf,int avg=0,int hig=-inf):low(low),avg(avg),hig(hig){total = cnt = 0;} }; struct Merchandise { int index,price; string name,dealer; bool completed; Merchandise(int index=-inf,string dealer="x",string name="x",int price=-inf):index(index),price(price),name(name),dealer(dealer){completed = false;} bool operator < (const Merchandise &a)const { if(price == a.price)return index < a.index; return price < a.price; } }; int n; bool cmp(const Merchandise &a,const Merchandise &b)//use this method to sort the vector Buy { if(a.price == b.price)return a.index < b.index; return a.price > b.price; } int main() { while(cin >> n,n) { map<string,ii> dealer; map<string,P> commodity; vector<Merchandise> Sell,Buy; rep(i,n) { string sdealer,name,order; int price; cin >> sdealer >> order >> name >> price; dealer[sdealer] = dealer[sdealer]; if(order[0] == 'S') { Sell.push_back(Merchandise(i,sdealer,name,price)); int index = Sell.size()-1; int bsize = Buy.size(); rep(j,bsize) { if(Buy[j].completed)continue; if(Buy[j].dealer == sdealer)continue; if(Buy[j].name == name && Buy[j].price >= price) { //cout << "Sell " << sdealer << " the commodity " << name << " to " << Buy[j].dealer << endl; Buy[j].completed = true; Sell[index].completed = true; int value = (int)floor((Buy[j].price+price)/2.0); dealer[Buy[j].dealer].first += value; dealer[sdealer].second += value; commodity[name].low = min(commodity[name].low,value); commodity[name].hig = max(commodity[name].hig,value); commodity[name].total += value; commodity[name].cnt++; break; } } sort(all(Sell)); } else { Buy.push_back(Merchandise(i,sdealer,name,price)); int index = Buy.size()-1; int ssize = Sell.size(); rep(j,ssize) { if(Sell[j].completed)continue; if(Sell[j].dealer == sdealer)continue; if(Sell[j].name == name && Sell[j].price <= price) { //cout << "Buy " << sdealer << " the commodity " << name << " from " << Sell[j].dealer << endl; Sell[j].completed = true; Buy[index].completed = true; int value = (int)floor((Sell[j].price+price)/2.0); dealer[Sell[j].dealer].second += value; dealer[sdealer].first += value; commodity[name].low = min(commodity[name].low,value); commodity[name].hig = max(commodity[name].hig,value); commodity[name].total += value; commodity[name].cnt++; break; } } sort(all(Buy),cmp); } } for(map<string,P>::iterator it = commodity.begin(); it != commodity.end(); it++) { cout << (it->first) << " " << (it->second.low) << " " << (int)floor((it->second.total)/(it->second.cnt)) << " " << (it->second.hig) << endl; } cout << "--" << endl; for(map<string,ii>::iterator it = dealer.begin();it != dealer.end();it++) { cout << (it->first) << " " << (it->second.first) << " " << (it->second.second) << endl; } cout << "----------" << endl; } return 0; }