The Java Program: balloons.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 
  5 public class balloons 
  6 {
  7     public Scanner sc;
  8     public PrintStream ps;
  9     
 10     /**
 11      * An object to hold the info about a team. 
 12      */
 13     public class Team implements Comparable<Team>
 14     {
 15         public int number, distances[], prefer, difference; 
 16         
 17         /**
 18          * Construct a team.
 19          * 
 20          * @param n Number of balloons the team needs
 21          * @param d0 Distance to room A
 22          * @param d1 Distance to room B
 23          */
 24         public Team( int n, int d0, int d1 )
 25         {
 26                 number = n;
 27                 distances = new int[2];
 28                 distances[0] = d0;
 29                 distances[1] = d1;
 30                 
 31                 // Which room is preferable? (The one with the smallest distance)
 32                 prefer = d0<d1 ? 0 : 1;
 33                 
 34                 // This is important - we need to know the difference, so we can sort on it.
 35                 difference = Math.abs( d1-d0 );
 36         }
 37         
 38         /**
 39          * Compare this Team to another Team, for sorting. The comparison is solely by
 40          * the difference in distances.
 41          * 
 42          * @param t The other team
 43          * @return Negative if this team should come before Team t, positive if it's the other way, zero if they're equal.
 44          */
 45         public int compareTo( Team t )
 46         {
 47                 return t.difference - difference;
 48         }
 49         
 50         /**
 51          * Create a pretty String describing the team for debugging.
 52          * 
 53          * @return A pretty String version of the Team
 54          */
 55         public String toString()
 56         {
 57                 return "{Team: n=" + number + ", d0=" + distances[0] + ", d1=" + distances[1]
 58                     + ", prefer=" + prefer + ", difference=" + difference + "}";
 59         }
 60     }
 61        
 62     /**
 63      * Driver.
 64      * @throws Exception
 65      */
 66     public void doit() throws Exception
 67     {
 68         sc = new Scanner( new File( "balloons.judge" ) );
 69         ps = new PrintStream( new FileOutputStream( "balloons.out" ) ); 
 70         int s[] = new int[2];
 71         
 72         for(;;)
 73         {
 74                 int n = sc.nextInt();
 75                 if( n==0 ) break;
 76                 
 77                 // s[0] is the number of balloons in room A, s[1] is B
 78                 s[0] = sc.nextInt();
 79                 s[1] = sc.nextInt();
 80                 
 81                 Team teams[] = new Team[n];
 82                 for( int i=0; i<n; i++ )
 83                 {
 84                         int k = sc.nextInt();
 85                         int d0 = sc.nextInt();
 86                         int d1 = sc.nextInt();
 87                         teams[i] = new Team( k, d0, d1 );
 88                 }
 89                 
 90                 // We're going to use a Greedy algorithm, and service the teams with the
 91                 // greatest difference in distances to A and B first. 
 92                 // So, we'll start by sorting them in that order.
 93                 Arrays.sort( teams );
 94                 
 95                 // Now, just go through the teams in order.
 96                 int total = 0;
 97                 for( Team team : teams )
 98                 {
 99                         // p is the preferred room, q is the other room
100                         int p = team.prefer;
101                         int q = 1-p;
102                         if( s[p] >= team.number )
103                         {
104                         // If there's enough, take them all from the preferred room
105                         total += team.number * team.distances[p];
106                         s[p] -= team.number;
107                         }
108                         else
109                         {
110                                 // Otherwise, take all that's left from the preferred room...
111                         total += s[p]* team.distances[p];
112                         team.number -= s[p];
113                         s[p] = 0;
114                                 
115                         // ...and take the rest from the other room.
116                         total += team.number * team.distances[q];
117                         s[q] -= team.number;
118                         }
119                 }
120                 
121             ps.println( total );
122             System.out.println( total );
123         }
124     }
125     
126     /**
127      * The main just creates an object and calls doit().
128      * 
129      * @param args Command line args, necessary but unused.
130      * @throws Exception
131      */
132         public static void main( String[] args ) throws Exception
133         {
134         new balloons().doit();
135         }
136 
137 }