http://snippets.dzone.com/posts Tue, 07 Oct 2008 09:03:10 GMT DZone Snippets: 10026 code http://snippets.dzone.com/posts/show/5357 A solution for the "Shoemaker" problem. <br /> <br />Problem description: <br /><a href="http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10026.html">http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10026.html</a> <br /> <br />Author: <a href="http://joanatrindade.wikidot.com">Joana Matos Fonseca da Trindade</a> <br />Date: 2008.04.06 <br /> <br /><code> <br />/* <br /> * Solution for "Shoemaker" problem. <br /> * UVa ID: 10026 <br /> */ <br />#include <iostream> <br /> <br />#define NJOBS 1000 <br /> <br />using namespace std; <br /> <br />int jobs[NJOBS]; /* jobs */ <br />double p[NJOBS]; /* priority */ <br /> <br />/* main */ <br />int main() { <br /> int nc; /* number of cases */ <br /> int nj; /* number of jobs */ <br /> int ct; /* completion time */ <br /> int dp; /* daily penalty */ <br /> <br /> cin >> nc; <br /> <br /> /* for each test case.. */ <br /> for (int i=0; i<nc; i++) { <br /> cin >> nj; <br /> <br /> /* init input */ <br /> for (int i=0; i<nj; i++) { <br /> cin >> ct >> dp; <br /> jobs[i] = i; <br /> /* priority is daily penalty divided by completion time (minimal fine) */ <br /> p[i] = double(dp) / ct; <br /> } <br /> <br /> int j, k, tmp; <br /> <br /> /* sort jobs by priority */ <br /> for (int i=0; i<nj-1; i++) { <br /> for (j=i+1, k=i; j<nj; j++) { <br /> if( (p[jobs[j]] > p[jobs[k]]) || ((p[jobs[j]] == p[jobs[k]]) && (jobs[j] < jobs[k])) ) { <br /> k=j; <br /> } <br /> } <br /> tmp = jobs[i]; <br /> jobs[i] = jobs[k]; <br /> jobs[k] = tmp; <br /> } <br /> <br /> /* output */ <br /> for (int i=0; i<nj; i++) { <br /> if(i > 0) { <br /> cout << " "; <br /> } <br /> cout << jobs[i] + 1; <br /> } <br /> cout << endl; <br /> if (i < nc-1) { <br /> cout << endl; <br /> } <br /> } <br /> <br /> return 0; <br />} <br /> <br /></code> Mon, 14 Apr 2008 01:02:22 GMT http://snippets.dzone.com/posts/show/5357 jmftrindade (Joana M. F. da Trindade)