首页 > 代码库 > hdu--2852--树状数组
hdu--2852--树状数组
擦 这题 绝逼 坑人 + 一波N折。。。。
touch me
我一开始 用了最简单 最sb的 一维hash数组 来做 我看时间2000ms最大数才10W 还以为能过的 ...果断tle了
然后 就觉得应该用更高效的数据结构来做了
我去问下了下porker 他一开始和我提了下 splay 不会啊=-=
然后 说 树状数组 + 查询的时候 用二分 也可以做到
我就去往 这个方向去想了--------TM的被自己思维定势了... tree[x]把它固定成X有几个了... 然后就一直没做出来
后来 参考了传送
最TM坑的是 我用cin cout一直TLE明明已经写了cin.sync..............
然后改成scanf printf 看A了之后 再改回来 再交 又TLE了
卧槽...
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 100010; 6 int tree[size];// tree[x] 即 小于等于x的数有几个 7 8 int lowbit( int x ) 9 { 10 return x & -x; 11 } 12 13 void update( int x , int var ) 14 { 15 while( x<size ) 16 { 17 tree[x] += var; 18 x += lowbit(x); 19 } 20 } 21 22 int getNum( int x ) 23 { 24 int cnt = 0; 25 while( x ) 26 { 27 cnt += tree[x]; 28 x -= lowbit(x); 29 } 30 return cnt; 31 } 32 33 int find( int x , int k ) 34 { 35 int l = x+1 , r = size-5 , ans = size , mid; 36 int temp = getNum(x); 37 int val; 38 while( l<r ) 39 { 40 mid = l + (r-l)/2; 41 val = getNum(mid) - temp; 42 if( val<k ) 43 { 44 l = mid+1; 45 } 46 else 47 { 48 r = mid; 49 if( ans > mid ) 50 ans = mid; 51 } 52 } 53 return ans; 54 } 55 56 int main() 57 { 58 cin.sync_with_stdio(false); 59 int n , num , m ,ans , k; 60 while( cin >> n ) 61 { 62 memset( tree , 0 , sizeof(tree) ); 63 while( n-- ) 64 { 65 //scanf("%d",&m); 66 cin >> m; 67 if( !m ) 68 { 69 //scanf("%d",&num); 70 cin >> num; 71 update( num , 1 ); 72 } 73 else if( m==1 ) 74 { 75 //scanf("%d",&num); 76 cin >> num; 77 if( getNum(num) - getNum(num-1) == 0 ) 78 { 79 //printf("No Elment!\n"); 80 cout << "No Elment!" << endl; 81 } 82 else 83 { 84 update( num , -1 ); 85 } 86 } 87 else 88 { 89 //scanf("%d %d",&num,&k); 90 cin >> num >> k; 91 ans = find( num , k ); 92 if( ans == size ) 93 //printf("Not Find!\n"); 94 cout << "Not Find!" << endl; 95 else 96 //printf("%d\n",ans); 97 cout << ans << endl; 98 } 99 }100 }101 return 0;102 }
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 100010; 6 int hash[size]; 7 8 int main() 9 {10 cin.sync_with_stdio(false);11 int m , k , num , maxNum , cnt , choice;12 bool flag;13 while( cin >> m )14 {15 maxNum = 0;16 memset( hash , 0 , sizeof(hash) );17 while( m-- )18 {19 cin >> choice;20 if( !choice )21 {22 cin >> num;23 hash[num] ++;24 if( maxNum < num )25 maxNum = num;26 }27 else if( choice == 1 )28 {29 cin >> num;30 if( hash[num] )31 {32 hash[num] --;33 }34 else35 {36 cout << "No Elment!" << endl;37 }38 }39 else40 {41 flag = false;42 cnt = 0;43 cin >> num >> k;44 for( int i = num+1 ; i<=maxNum ; i++ )45 {46 if( hash[i] )47 {48 cnt += hash[i];49 if( cnt>=k )50 {51 cout << i << endl;52 flag = true;53 break;54 }55 }56 }57 if( !flag )58 cout << "Not Find!" << endl;59 }60 }61 }62 return 0;63 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。