The C++ Program: balloons_rds.cpp

  1 #include <iostream>
  2 #include <fstream>
  3 #include <cstdlib>
  4 using namespace std;
  5 
  6 typedef struct _Team {
  7    int numBalloons;
  8    int distA;
  9    int distB;
 10 } Team;
 11 
 12 // The teams who has most to benefit by going to room A, goes first
 13 int compare (const void * ptr1, const void * ptr2) {
 14    const Team* team1 = (Team*) ptr1;
 15    const Team* team2 = (Team*) ptr2;
 16    const int diff1 = (team1->distA - team1->distB);
 17    const int diff2 = (team2->distA - team2->distB);
 18    if (diff1==diff2) return 0;
 19    return (diff1 > diff2)?+1:-1;
 20 }
 21 
 22 int main() {
 23    int numTeams, numA, numB;
 24    while (true) {
 25       cin >> numTeams >> numA >> numB;
 26       if (numTeams<=0) break;
 27       int balloonsLeft = 0;
 28       Team teams[numTeams];
 29       for (int i = 0; i < numTeams; i++) {
 30          Team t;
 31          cin >>t.numBalloons >> t.distA >> t.distB ;
 32          balloonsLeft += t.numBalloons;
 33          teams[i] = t;
 34       }
 35       qsort (teams, numTeams, sizeof(Team), compare);
 36           
 37       int totalDist = 0;
 38       for (int i = 0; i < numTeams; i++) {
 39          Team team = teams[i];
 40               
 41          /* We want to decide how many of this team's balloons will come 
 42             from A vs. B.
 43          */
 44          int teamACount = 0;
 45          int teamBCount = 0;
 46               
 47          if (team.distA <= team.distB && numA >= team.numBalloons) {
 48             /*
 49               Case 1 : distA <= distB, and there are enough A balloons left
 50               for the whole team. Get all balloons from A.
 51             */
 52             teamACount = team.numBalloons;
 53          } else if (team.distA <= team.distB) {
 54             /*
 55               Case 2 : distA <= distB, and there are NOT enough A balloons 
 56               left for the whole team. Get "numA" balloons from A, and the
 57               rest from B.
 58             */
 59             teamACount = numA;
 60             teamBCount = team.numBalloons - teamACount;
 61          } else if (numB >= balloonsLeft) {
 62               
 63             /*
 64               Case 3 : distA > distB, and there are enough B balloons left
 65               for all the remaining teams. Get all balloons from B.
 66             */
 67 
 68             teamBCount = team.numBalloons;
 69          } else {
 70               
 71             /*
 72               Case 4 : distA > distB, and there are NOT enough B balloons 
 73               left for all the remaining teams. Leave enough B balloons for
 74               all the other teams, then take any remaining B balloons. Take
 75               the rest from A.
 76             */
 77             int bAllowed = (numB - (balloonsLeft - team.numBalloons));
 78             bAllowed = max(bAllowed, 0);
 79             teamBCount = bAllowed;
 80             teamACount = team.numBalloons - bAllowed;
 81          }
 82               
 83          // Now that we've picked numA and numB, update all the counts.
 84          totalDist += team.distA * teamACount;
 85          totalDist += team.distB * teamBCount;
 86          numA -= teamACount;
 87          numB -= teamBCount;
 88          balloonsLeft -= team.numBalloons;           
 89       }
 90       cout << totalDist << endl;
 91    }
 92    return 0;
 93 }
 94 
 95 /*  ------------For GNU Emacs ------------
 96     Local Variables:
 97     compile-command: "g++ balloons_rds.cpp -o balloons"
 98     End:
 99 */