Posted on 2008-10-01 17:17
Hero 閱讀(173)
評論(1) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //5082 Accepted C++ 0.0500 s 424 k HRBEU
2
3 //貪心---線性掃描
4
5 #include <iostream>
6 #include <algorithm>
7
8 using namespace std ;
9
10 const int size = 1001000 ;
11
12 int muss[size] ;
13 int cult[size] ;
14
15 int inn, inm ;
16 int cnt ;
17
18
19 int cmp( const void *a, const void *b )
20 {
21 return (int *)a - (int *)b ;
22 }
23
24 int main()
25 {
26 while( scanf( "%d %d", &inn, &inm ) != EOF )
27 {
28 for( int i=1; i<=inn; i++ ) scanf( "%d", &cult[i] ) ;
29 for( int i=1; i<=inm; i++ ) scanf( "%d", &muss[i] ) ;
30
31 sort( muss+1, muss+1+inm ) ;
32
33 int pcult = 1 ; int pmuss = 1 ; cnt = 0 ;
34
35 for( pcult=1; pcult<=inn; pcult++ )
36 {
37 while( muss[pmuss] < pcult && pmuss<=inm ) pmuss++ ;
38
39 while( cult[pcult] > 0 )
40 {
41 if( pmuss > inm ) break ;
42 pmuss++ ; cult[pcult]-- ; cnt++ ;
43 }
44
45 if( pmuss > inm ) break ;
46 }
47
48 printf( "%d\n", cnt ) ;
49 }
50
51 return 0 ;
52 }