読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

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