Posted on 2008-09-19 18:36
Hero 閱讀(164)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
代碼如詩(shī)－－ACM
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <algorithm>
5 #include <iostream>
6 using namespace std ;
7
8 const int size = 30 ;
9
10 int f[size], d[size], t[size] ;
11 int laketime[size] ;
12 int finaltime[size] ;
13
14 struct Lake
15 {
16 int fish ;//可掉的魚(yú)的數(shù)量
17 int num ;//該湖的序號(hào)
18 friend bool operator<( const Lake &a, const Lake &b ) ;
19 };
20 struct Lake lake[size] ;
21
22 bool operator<( const Lake &a, const Lake &b )
23 {
24 if( a.fish != b.fish ) return a.fish - b.fish < 0 ;
25
26 return a.num - b.num > 0 ;
27 }
28
29 int inn, inh ;
30 int maxfish ;
31
32 void input()
33 {
34 scanf( "%d", &inh ) ; inh = inh*60/5 ;
35 for( int i=1; i<=inn; i++ ) scanf( "%d", &f[i] ) ;
36 for( int i=1; i<=inn; i++ ) scanf( "%d", &d[i] ) ;
37
38 for( int i=1; i<inn; i++ ) scanf( "%d", &t[i] ) ;
39 }
40
41 void process()
42 {
43 maxfish = -1 ; int curfish ;
44 for( int nlake=1; nlake<=inn; nlake++ )
45 {//枚舉湖的數(shù)量
46 for( int i=1; i<=inn; i++ )
47 {
48 lake[i].fish = f[i] ; lake[i].num = i ; laketime[i] = 0 ;
49 }
50 make_heap( lake+1, lake+1+nlake ) ;//構(gòu)造大頂堆
51
52 memset( laketime, 0, sizeof(laketime) ) ;
53 curfish = 0 ; int maxi = inh ;
54 for( int i=1; i<nlake; i++ ) maxi -= t[i] ;
55 for( int i=1; i<=maxi; i++ )
56 {
57 //出堆--最值放在最后一個(gè)位置
58 pop_heap( lake+1, lake+1+nlake ) ;
59
60 int num = lake[1+nlake-1].num ;
61 int fish = lake[1+nlake-1].fish ;
62
63 curfish += fish ; laketime[num]++ ;
64
65 lake[1+nlake-1].fish -= d[num] ;
66 if( lake[1+nlake-1].fish < 0 ) lake[1+nlake-1].fish = 0 ;
67
68 push_heap( lake+1, lake+1+nlake ) ;//入堆--重新調(diào)整
69 }
70
71 if( curfish > maxfish )
72 {
73 maxfish = curfish ;
74 memcpy( finaltime, laketime, sizeof(finaltime) ) ;
75 //for( int i=0; i<=inn; i++ ) finaltime[i] = laketime[i] ;
76 }
77 }
78 }
79
80 void output()
81 {
82 printf( "%d", finaltime[1]*5 ) ;
83 for( int i=2; i<=inn; i++ )
84 {
85 printf( ", %d", finaltime[i]*5 ) ;
86 }
87 printf( "\nNumber of fish expected: %d\n\n", maxfish ) ;
88 }
89
90 int main()
91 {
92 //freopen( "in.txt", "r", stdin ) ;
93 //freopen( "out.txt", "w", stdout ) ;
94
95 while( scanf( "%d", &inn ) != EOF && inn )
96 {
97 input() ;
98
99 process() ;
100
101 output() ;
102 }
103
104 return 0 ;
105 }
106