The Java Program: Balloons.java

  1 import java.io.*;
  2 import java.util.Arrays;
  3 import java.util.Scanner;
  4 
  5 public final class Balloons {
  6 
  7    /**
  8     * An object to hold the info about a team. 
  9     */
 10    public static class Team implements Comparable<Team> {
 11       public final int number, distances[], prefer, difference; 
 12       private static int counter=0;
 13       private int id = counter++;
 14         
 15       /**
 16        * Construct a team.
 17        * 
 18        * @param n Number of balloons the team needs
 19        * @param d0 Distance to room A
 20        * @param d1 Distance to room B
 21        */
 22       public Team (int n, int d0, int d1) {
 23          number = n;
 24          distances = new int[]{d0,d1};
 25          // The closest room is preferable
 26          prefer = d0<d1 ? 0 : 1;
 27          difference = Math.abs (d1-d0);
 28       }
 29         
 30       public int compareTo (Team t) {
 31          if (t.difference < difference) return -1;
 32          if (t.difference > difference) return +1;
 33          if (t.id < id) return -1;
 34          if (t.id > id) return +1;
 35          assert this.equals (t);
 36          return 0;
 37       }
 38         
 39       public String toString() {
 40          return String.format ("{Team %d: n=%d, dist=(%d,%d), diff=%d}",
 41             id, number, distances[0], distances[1], difference);
 42       }
 43    }
 44        
 45    private static final Scanner STDIN =
 46       new Scanner (new BufferedInputStream (System.in));
 47 
 48    public static void main (String[] args) {
 49         
 50       for(;;) {
 51          final int n = STDIN.nextInt(); // number of teams
 52          if (n==0) break;
 53                 
 54          final int a = STDIN.nextInt();  // initial number of balloons in room A
 55          assert 0<=a && a<=10000;
 56          final int b = STDIN.nextInt();  // initail number of balloons in room B
 57          assert 0<=b && b<=10000;
 58          final int[] s = {a,b};
 59                 
 60          Team teams[] = new Team[n];
 61          for (int i=0; i<n; i++) {
 62             final int k = STDIN.nextInt();
 63             final int d0 = STDIN.nextInt();
 64             final int d1 = STDIN.nextInt();
 65             teams[i] = new Team (k, d0, d1);
 66          }
 67                 
 68          // We're going to use a Greedy algorithm, and service the teams with the
 69          // greatest difference in distances to A and B first. 
 70          // So, we'll start by sorting them in that order.
 71          Arrays.sort (teams);
 72                 
 73          // Now, just go through the teams in order.
 74          int total = 0;
 75          for (Team team : teams) {
 76             assert team.number < s[0]+s[1];
 77             System.out.print (team);
 78 
 79             // p is the preferred room, q is the other room
 80             final int p = team.prefer;
 81             final int q = 1-p;
 82             if (s[p] >= team.number) {
 83                // If there's enough, take them all from the preferred room
 84                total += team.number * team.distances[p];
 85                s[p] -= team.number;
 86             } else {
 87                // Otherwise, take all that's left from the preferred room...
 88 
 89                // Number of balloons from the non-prefered room
 90                final int rest = team.number - s[p];  
 91                total += s[p]* team.distances[p];
 92                s[p] = 0;
 93                                 
 94                // ...and take the rest from the other room.
 95                total += rest * team.distances[q];
 96                s[q] -= rest;
 97             }
 98             System.out.printf ("%d %d %d%n", s[0],s[1],total);
 99          }
100          
101          System.out.println (total);
102       }
103    }
104 }
105 
106 /*
107   %%% Local Variables:
108   %%% compile-command: "javac Balloons.java"
109   %%% End:
110 */