Posted on 2008-12-14 00:28
Hero 阅读(130)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
1 // 1290 C++ Accepted 0.031 629 KB URAL
2
3 //树状数组--统计类问题
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int size = 25100*2 ;
10 int Tarry1[size+10] ; int Tnum1 ;
11 int Tarry2[size+10] ; int Tnum2 ;
12 int out[size+10] ;
13
14 int inn, inm ;
15
16 int Lowbit( int e )
17 {
18 return e & (-e) ;
19 }
20
21 int fsum( int n, int arry[] )
22 {
23 int sum = 0 ;
24 while( n > 0 )
25 {
26 sum += arry[n] ;
27 n = n - Lowbit(n) ;
28 }
29 return sum ;
30 }
31
32 void fadd( int pos, int num, int arry[] )
33 {
34 while( pos <= size )
35 {
36 arry[pos] += num ;
37 pos += Lowbit( pos ) ;
38 }
39 }
40
41 int main()
42 {
43 while( scanf( "%d", &inn ) != EOF )
44 {
45 if( 0 == inn ) continue ;
46
47 memset( Tarry1, 0, sizeof(Tarry1) ) ;
48 memset( Tarry2, 0, sizeof(Tarry2) ) ;
49
50 int num ; int maxnum = -100 ;
51 for( int i=1; i<=inn; i++ )
52 {
53 scanf( "%d", &num ) ;
54 fadd( num, 1, Tarry1 ) ;
55 }
56
57 inm = 0 ;
58 for( int i=1; ; i++ )
59 {
60 Tarry2[i] = fsum( i, Tarry1 ) ;
61 Tarry2[i] = inn - Tarry2[i] ;
62 if( 0 == Tarry2[i] ) break ;
63 inm = inm + 1 ;
64 }
65 Tarry2[0] = inn ;
66
67 memset( Tarry1, 0, sizeof(Tarry1) ) ;
68 for( int i=0; i<=inm; i++ )
69 {
70 fadd( Tarry2[i], 1, Tarry1 ) ;
71 }
72
73 printf( "%d\n", ++inm ) ;
74
75 for( int i=1; ; i++ )
76 {
77 out[i] = inm - fsum( i, Tarry1 ) ;
78 if( 0 >= out[i] ) break ;
79 else printf( "%d\n", out[i] ) ;
80 }
81 }
82
83 return 0 ;
84 }