The Java Program: YiuBalloon.java

  1 /*
  2 ACM ICPC Southeast USA Regional Contest 2010
  3 Problem: Balloon
  4 
  5 Author: Yiu Yu Ho
  6 */
  7 
  8 import java.io.*;
  9 import java.util.*;
 10 
 11 public class YiuBalloon
 12 {
 13         public Scanner in = new Scanner(System.in);
 14         public PrintStream out = System.out;
 15 
 16     public int n, A, B;
 17     public int Ar, Br;
 18     
 19     public ArrayList<Team> Av, Bv;
 20     
 21         public void main() throws Exception
 22         {
 23             in = new Scanner( new File( "balloons.judge" ) );
 24             out = new PrintStream( new FileOutputStream( "balloonsyiu.out" ) );
 25         n = in.nextInt();
 26         while(n > 0)
 27         {
 28             A = in.nextInt();
 29             B = in.nextInt();
 30             
 31             Ar = Br = 0;
 32             Av = new ArrayList<Team>();
 33             Bv = new ArrayList<Team>();
 34             
 35             int K, DA, DB;
 36             int res = 0;
 37             
 38             for(int i = 0; i < n; ++i)
 39             {
 40                 K = in.nextInt();
 41                 DA = in.nextInt();
 42                 DB = in.nextInt();
 43                 
 44                 if(DA < DB)
 45                 {
 46                     Ar += K;
 47                     res += DA * K;
 48                     Av.add(new Team(K, DB - DA));
 49                 }
 50                 else
 51                 {
 52                     //DA >= DB
 53                     Br += K;
 54                     res += DB * K;
 55                     Bv.add(new Team(K, DA - DB));
 56                 }
 57             }
 58             
 59             Collections.sort(Av);
 60             Collections.sort(Bv);
 61             
 62             if(Ar > A) res += move(Ar - A, Av);
 63             if(Br > B) res += move(Br - B, Bv);
 64             
 65             out.println(res);
 66             
 67             n = in.nextInt();
 68         }
 69         }//end public void main()
 70 
 71     public int move(int mv, ArrayList<Team> v)
 72     {
 73         int res = 0;
 74         for(int i = 0; i < v.size() && mv > 0; ++i)
 75         {
 76             Team T = v.get(i);
 77             if(T.count < mv)
 78             {
 79                 res += T.count * T.cost;
 80                 mv -= T.count;
 81             }
 82             else
 83             {
 84                 //T.count >= mv
 85                 res += mv * T.cost;
 86                 mv -= mv;
 87             }
 88         }
 89         
 90         return res;
 91     }
 92     
 93     private class Team implements Comparable<Team>
 94     {
 95         public int cost, count;
 96         
 97         public Team(int countIn, int costIn)
 98         {
 99             cost = costIn;
100             count = countIn;
101         }
102         
103         //smallest cost first
104         public int compareTo(Team T)
105         {
106             if(cost != T.cost) return cost - T.cost;
107             return count - T.count;
108         }
109     }
110     
111         public static void main(String[] args) throws Exception
112         {
113                 (new YiuBalloon()).main();
114         }
115 }