当前位置: 代码迷 >> 综合 >> KiKi‘s K-Number HDU - 2852(树状数组+二分在整个数组里查找比x大的第k个数)
  详细解决方案

KiKi‘s K-Number HDU - 2852(树状数组+二分在整个数组里查找比x大的第k个数)

热度:46   发布时间:2024-01-31 03:55:05.0

hdu2852
题解:我们的c[i]维护的是值为i的个数,每次我们查询值小于i的数的个数我们可以借用树状数组里查询前缀和的思想进行query(i)便可,之后我们就可以在树状数组上进行二分。
时间复杂度(nlognlogn),不够优秀!!!

#include<bits/stdc++.h>//emuB167202003070038
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
int c[maxn];
int sum;
void init()
{for(int i=0;i<maxn;i++){c[i]=0;}
}
void add(int x,int d)
{while(x<maxn){c[x]+=d;x+=(x&(-x));}
}
int query(int x)
{int res=0;while(x>0){res+=c[x];x-=(x&(-x));}return res;
}
bool judge(int x,int y)
{int ko=query(x)-sum;return ko>=y;
}
int main()
{int m;while(scanf("%d",&m)!=EOF){init();while(m--){int op;scanf("%d",&op);if(op==0){int x;scanf("%d",&x);add(x,1);}elseif(op==1){int x;scanf("%d",&x);if(query(x)-query(x-1)>0){add(x,-1);}else{printf("No Elment!\n");}}else{int x,k;scanf("%d%d",&x,&k);int l=x,r=maxn-1;int ans=-1;sum=query(x);while(l<=r){int mid=(l+r)>>1;if(judge(mid,k)){ans=mid;r=mid-1;}else{l=mid+1;}}if(ans==-1){printf("Not Find!\n");}else{printf("%d\n",ans);}}}}return 0;
}
  相关解决方案