首页 > 代码库 > hdu 4217Data Structure?
hdu 4217Data Structure?
树状数组+二分
就是找第几小的数,,找几次,再求和。。
#include<cstdio> #include<cstring> #include<iostream> #include<queue> #include<algorithm> using namespace std; const int N=277777; int t,n,m,bit[N],num,i; long long ans; int low(int g) { return g&(-g); } void update(int pos) { while(pos<=n) { bit[pos]--; pos+=low(pos); } } int query(int x) { int sum=0; while(x>0) { sum+=bit[x]; x-=low(x); } return sum; } int Sum(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; } void init() { ans=0; memset(bit,0,sizeof(bit)); scanf("%d %d",&n,&m); for(i=1;i<=n;i++) {bit[i]=low(i);} for(i=0;i<m;i++) { scanf("%d",&num); int s=Sum(num); update(s); ans+=s; } } int main() { int cas=0; scanf("%d",&t); while(t--) { init(); cout<<"Case "<<++cas<<": "<<ans<<endl; } return 0; }
二分查找详解点击打开链接
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。