HDU 4217 Data Structure? 树状数组

发布时间:2014-10-22 14:52:07编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 4217 Data Structure? 树状数组",主要涉及到HDU 4217 Data Structure? 树状数组方面的内容,对于HDU 4217 Data Structure? 树状数组感兴趣的同学可以参考一下。

Data Structure? Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2166    Accepted Submission(s): 692 Problem Description Data structure is one of the basic skills for Computer Science students, which is a particular way of storing and organizing data in a computer so that it can be used efficiently. Today let me introduce a data-structure-like problem for you. Original, there are N numbers, namely 1, 2, 3...N. Each round, iSea find out the Ki-th smallest number and take it away, your task is reporting him the total sum of the numbers he has taken away.   Input The first line contains a single integer T, indicating the number of test cases. Each test case includes two integers N, K, K indicates the round numbers. Then a line with K numbers following, indicating in i (1-based) round, iSea take away the Ki-th smallest away. Technical Specification 1. 1 <= T <= 128 2. 1 <= K <= N <= 262 144 3. 1 <= Ki <= N - i + 1   Output For each test case, output the case number first, then the sum.   Sample Input 2 3 2 1 1 10 3 3 9 1   Sample Output Case 1: 3 Case 2: 14   Author iSea@WHU   Source 首届华中区程序设计邀请赛暨第十届武汉大学程序设计大赛   不知道为什么。。。我用long long 交到GCC编译器上就是一直wa。  然后改__int64才过掉的。。 // // 4217.cpp // ACM_HDU // // Created by ipqhjjybj on 13-9-8. // Copyright (c) 2013年 ipqhjjybj. All rights reserved. // #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> using namespace std; #define lowbit(x) (x&(-x)) const int MAXN=333333; int n,k; int a[MAXN]; #define LL __int64 void Update(int pos){ while(pos<=n){ a[pos]--; pos+=lowbit(pos); } } int Query(int pos){ int sum=0; while(pos>0){ sum+=a[pos]; pos-=lowbit(pos); } return sum; } int Bisearch(int k){ int l=1,r=n,mid; while(l<r){ mid=(l+r)>>1; if(Query(mid)>=k) r=mid; else l=mid+1; } return l; } int main(){ int t,tmp,tt=0; LL sum; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&k); sum=0; for(int i=0;i<=n;i++) a[i]=lowbit(i); while(k--){ scanf("%d",&tmp); tmp=Bisearch(tmp); Update(tmp); sum+=tmp; } cout<<"Case "<<++tt<<": "<<sum<<endl; //printf("Case %d: %lld\n",++tt,sum); } return 0; } 我原本的查找代码: int Bisearch(int k){ int l=1,r=n,mid; while(l<=r){ mid=(l+r)>>1; int tmp=Query(mid)+mid; if(tmp==k){ return mid; }else if(tmp<k){ l=mid+1; }else r=mid-1; } return l; } 在这题是错误的 。  因为它没有考虑到这样的情况。   假设第8个数据是0,这样前7个数据跟前8个数据和是相等的。 这样我们就可能查找到错误的8了。 所以,我们要保证查找到的是最左边的前tmp项和==k。。  这里我wa了好多次。

下一篇:写了个 大家经常会用到的 Tab 切换 效果