Posted on 2008-10-11 15:21
Hero 閱讀(154)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 #include <stdio.h>
2 #include <math.h>
3 #include <string.h>
4 #include <stdlib.h>
5
6 //#define myDebug 1 ;
7
8 const int INF = 10010000 ;
9 const int size = 50100 ;
10
11 int data[size] ;
12
13 int inm, inn ;
14 int out ;
15
16 int cmp( const void *a, const void *b )
17 {
18 return *(int *)a - *(int *)b ;
19 }
20
21 void input()
22 {
23 for( int i=1; i<=inn; i++ ) scanf( "%d", &data[i] ) ;
24
25 data[inn+1] = INF ; data[0] = -1*INF ;
26 qsort( data+1, inn, sizeof(data[1]), cmp ) ;
27
28 #ifdef myDebug
29 {
30 for( int i=1; i<=inn; i++ ) printf( "%d ", data[i] ) ;
31 printf( "\n" ) ;
32 }
33 #endif
34 }
35
36 void process()
37 {
38 int p1, p2 ; int pos0 ;
39
40 for( pos0=1; pos0<=inn&&data[pos0]<0; pos0++ ) ;
41
42 p1 = pos0-1; p2 = pos0 ; out = 0 ; int last = 0 ;
43
44 while( inm > 0 )
45 {
46 if( p1<=0 && p2>inn ) break ;
47
48 if( -1*data[p1] > data[p2] )
49 {
50 inm = inm - abs( last - data[p2] ) ;
51 if( inm < 0 ) break ;
52 else
53 {
54 out++ ; last = data[p2]; p2++ ;
55 }
56 }
57 else
58 {
59 inm = inm - abs(last - data[p1] ) ;
60 if( inm < 0 ) break ;
61 else
62 {
63 out++ ; last = data[p1] ; p1-- ;
64 }
65 }
66 }
67 }
68
69 void output()
70 {
71 printf( "%d\n", out ) ;
72 }
73
74 int main()
75 {
76 while( scanf( "%d %d", &inm, &inn ) != EOF )
77 {
78 input() ;
79
80 process() ;
81
82 output() ;
83 }
84
85 return 0 ;
86 }