1  
   2  /* 
   3   * Solution for "Shoemaker" problem.
   4   * UVa ID: 10026
   5   */
   6  #include <iostream>
   7  
   8  #define NJOBS 1000
   9  
  10  using namespace std;
  11  
  12  int jobs[NJOBS]; /* jobs */
  13  double p[NJOBS]; /* priority */
  14  
  15  /* main */
  16  int main() {
  17      int nc;	/* number of cases */
  18  	int nj; /* number of jobs */
  19  	int ct;	/* completion time */
  20  	int dp; /* daily penalty */
  21  	
  22      cin >> nc;
  23  	
  24  	/* for each test case.. */
  25      for (int i=0; i<nc; i++) {
  26  		cin >> nj;
  27  		
  28  		/* init input */
  29  		for (int i=0; i<nj; i++) {
  30  			cin >> ct >> dp;
  31  			jobs[i] = i;
  32  			/* priority is daily penalty divided by completion time (minimal fine) */
  33  			p[i] = double(dp) / ct;
  34  		}
  35  		
  36  		int j, k, tmp;
  37  		
  38  		/* sort jobs by priority */
  39  		for (int i=0; i<nj-1; i++) {
  40  			for (j=i+1, k=i; j<nj; j++) {
  41  				if( (p[jobs[j]] > p[jobs[k]]) || ((p[jobs[j]] == p[jobs[k]]) && (jobs[j] < jobs[k])) ) {
  42  					k=j;
  43  				}
  44  			}
  45  			tmp = jobs[i]; 
  46  			jobs[i] = jobs[k]; 
  47  			jobs[k] = tmp;
  48  		}
  49  		
  50  		/* output */
  51  		for (int i=0; i<nj; i++) {
  52  			if(i > 0) { 
  53  				cout << " ";
  54  			}
  55  			cout << jobs[i] + 1;
  56  		}
  57  		cout << endl;
  58  		if (i < nc-1) {
  59  			cout << endl;
  60  		}
  61      }
  62  	
  63      return 0;
  64  }
  65