1407 e-market

「1407 e-market」の編集履歴（バックアップ）一覧はこちら

「1407 e-market」(2006/04/16 (日) 23:06:24) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1407 e-market
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1407
**解答方針
出力は商品ごと，商人ごとに辞書順で行うことから，商品名から取引価格リストへのMap，人名から支出・収入へのMapをTreeMapで実装しておくと便利である．

シミュレーションの過程では，待機売り手リスト，待機買い手リストを保持しておき，新しい売り手または買い手が来る毎にルールに従った処理を行えばよい．
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             int n = sc.nextInt();
             if(n==0) break;
             
             ArrayList<Order> orders = new ArrayList<Order>();
             for(int i=0;i<n;i++){
                 String per = sc.next();
                 String sdtype = sc.next();
                 Ordertype dtype;
                 if(sdtype.equals("SELL")) dtype = Ordertype.SELL;
                 else dtype = Ordertype.BUY;
                 String com = sc.next();
                 int price = sc.nextInt();
                 orders.add(new Order(per,dtype,com,price));
             }
             Solver sol = new Solver(orders);
             sol.solve();
             sol.print();
         }
     }
 }
 
 class Solver{
     ArrayList<Order> orders;
     TreeMap<String,ArrayList<Integer>> comdeallist;
     TreeMap<String,PersonData> perdatalist;
     LinkedList<Order> buyers;
     LinkedList<Order> sellers;
 
     Solver(ArrayList<Order> sorders){
         orders = sorders;
         comdeallist = new TreeMap<String,ArrayList<Integer>>();
         perdatalist = new TreeMap<String,PersonData>();
         buyers = new LinkedList<Order>();
         sellers = new LinkedList<Order>();
         for(Order o:orders){
             if(!perdatalist.containsKey(o.person))
                 perdatalist.put(o.person,new PersonData());
             if(!comdeallist.containsKey(o.commodity))
                 comdeallist.put(o.commodity,new ArrayList<Integer>());
         }
     }
     public void solve(){
         for(Order o:orders){
             if(o.dtype==Ordertype.BUY){
                 newBuyer(o);
             }
             else{
                 newSeller(o);
             }
         }
     }
     private void newBuyer(Order buy){
         Order sell = null;
         for(Order s:sellers){
             if(s.commodity.equals(buy.commodity)&&s.price<=buy.price
                     &&!s.person.equals(buy.person)){
                 if(sell==null) sell = s;
                 else if(s.price<sell.price) sell = s;
             }
         }
         
         if(sell==null){
             buyers.add(buy);
         }
         else{
             sellers.remove(sell);
             int dealprice = (sell.price+buy.price)/2;
             comdeallist.get(sell.commodity).add(dealprice);
             perdatalist.get(sell.person).recv += dealprice;
             perdatalist.get(buy.person).pay += dealprice;
         }
     }
     private void newSeller(Order sell){
         Order buy = null;
         for(Order b:buyers){
             if(b.commodity.equals(sell.commodity)&&b.price>=sell.price
                     &&!b.person.equals(sell.person)){
                 if(buy==null) buy = b;
                 else if(b.price>buy.price) buy = b;
             }
         }
         
         if(buy==null){
             sellers.add(sell);
         }
         else{
             buyers.remove(buy);
             int dealprice = (sell.price+buy.price)/2;
             comdeallist.get(sell.commodity).add(dealprice);
             perdatalist.get(sell.person).recv += dealprice;
             perdatalist.get(buy.person).pay += dealprice;
         }
     }
     public void print(){
         Set<Map.Entry<String,ArrayList<Integer>>> comset = comdeallist.entrySet();
         for(Map.Entry<String,ArrayList<Integer>> c:comset){
             ArrayList<Integer> v = c.getValue();
             if(v.size()>0){
                 int min = Integer.MAX_VALUE;
                 int max = Integer.MIN_VALUE;
                 int sum = 0;
                 for(Integer i:v){
                     if(i<min) min = i;
                     if(i>max) max = i;
                     sum += i;
                 }
                 int avg = sum/v.size();
                 System.out.println(c.getKey()+" "+min+" "+avg+" "+max);
             }
         }
         System.out.println("--");
         
         Set<Map.Entry<String,PersonData>> perset = perdatalist.entrySet();
         for(Map.Entry<String,PersonData> p:perset){
             System.out.println(p.getKey()+" "+p.getValue().pay+" "+p.getValue().recv);
         }
         System.out.println("----------");
     }
 }
 
 class PersonData{
     int pay;
     int recv;
     PersonData(){
         pay = 0;
         recv = 0;
     }
 }
 
 class Order{
     String person;
     Ordertype dtype;
     String commodity;
     int price;
     Order(String oper,Ordertype odtype,String ocom,int oprice){
         person = oper;
         dtype = odtype;
         commodity = ocom;
         price = oprice;
     }
 }
 
 enum Ordertype{
     BUY,SELL;
 }