Posted on 2008-04-01 10:37
superman 閱讀(311)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1409 C++ 00:00.32 956K */
2 #include <stdlib.h>
3 #include <iostream>
4
5 using namespace std;
6
7 struct SYS { int b, p; } sys[100][100];
8
9 int cmp(const void * a, const void * b)
10 {
11 SYS * c = (SYS *) a;
12 SYS * d = (SYS *) b;
13 return c -> p - d -> p;
14 }
15
16 int main()
17 {
18 cout.setf(ios_base::showpoint);
19 cout.setf(ios_base::fixed);
20 cout.precision(3);
21
22 int n;
23 cin >> n;
24 while(cin >> n)
25 {
26 int m[100], b[10000], bc = 0;
27 for(int i = 0; i < n; i++)
28 {
29 cin >> m[i];
30 for(int j = 0; j < m[i]; j++)
31 {
32 cin >> sys[i][j].b >> sys[i][j].p;
33 b[bc++] = sys[i][j].b;
34 }
35 qsort(sys[i], m[i], sizeof(SYS), cmp);
36 }
37
38 double max = 0;
39 for(int k = 0; k < bc; k++)
40 {
41 int sum = 0;
42 bool could = true;
43 for(int i = 0; i < n; i++)
44 {
45 int j;
46 for(j = 0; j < m[i]; j++)
47 if(sys[i][j].b >= b[k])
48 {
49 sum += sys[i][j].p;
50 break;
51 }
52 if(j == m[i])
53 {
54 could = false;
55 break;
56 }
57 }
58 if(could)
59 max >?= double(b[k]) / sum;
60 }
61
62 cout << max << endl;
63 }
64
65
66 return 0;
67 }
68