博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 2852 KiKi's K-Number(树状数组+二分搜索)
阅读量:5262 次
发布时间:2019-06-14

本文共 1756 字,大约阅读时间需要 5 分钟。

题意:给出三种操作
  0 e:将e放入容器中
  1 e:将e从容器中删除,若不存在,则输出No Elment!
  2 a k:搜索容器中比a大的第k个数,若不存在,则输出Not Find!

思路:树状数组+二分搜索,具体见代码吧。

#include 
#include
#include
#include
/*AC树状数组+二分搜索题意:给出三种操作 0 e:将e放入容器中 1 e:将e从容器中删除,若不存在,则输出No Elment! 2 a k:搜索容器中比a大的第k个数,若不存在,则输出Not Find!思路:树状数组+二分搜索,具体见代码吧。*/using namespace std;const int maxn=100005;int m;int c[maxn]; //树状数组int vis[maxn]; //vis[i]表示元素i的个数int lowbit(int x){ return x&(-x);}void update(int i,int v){ while(i
1){ mid=(l+r)>>1; tmp=sum(mid); if(k<=tmp) r=mid; else l=mid; } return r;}int main(){ int op,e,k; int n; //目前存放的元素个数 while(scanf("%d",&m)!=EOF){ memset(vis,0,sizeof(vis)); memset(c,0,sizeof(c)); n=0; for(int i=1;i<=m;i++){ scanf("%d",&op); if(op==0){ scanf("%d",&e); vis[e]++; update(e,1); n++; } else if(op==1){ scanf("%d",&e); if(!vis[e]) printf("No Elment!\n"); else{ vis[e]--; update(e,-1); n--; } } else{ scanf("%d%d",&e,&k); int t=sum(e); // 目前<=e的元素有t个,转化成搜索第t+k个大的元素 //若t+k直接大于n,则不存在该元素 if(t+k>n) printf("Not Find!\n"); else{ k=k+t; printf("%d\n",binarySearch(k)); } } } } return 0;}

 

转载于:https://www.cnblogs.com/chenxiwenruo/p/3432450.html

你可能感兴趣的文章
Mysql 数据库操作
查看>>
转:linux终端常用快捷键
查看>>
009.栈实现队列
查看>>
A-Softmax的总结及与L-Softmax的对比——SphereFace
查看>>
关于软件盘覆盖住布局
查看>>
Unity3D 控制物体移动、旋转、缩放
查看>>
UVa 11059 最大乘积
查看>>
UVa 12545 比特变换器
查看>>
数组分割问题求两个子数组的和差值的小
查看>>
10个著名的思想实验1
查看>>
composer 报 zlib_decode(): data error
查看>>
linux下WPS的使用
查看>>
Web Api 利用 cors 实现跨域
查看>>
hdu 3938 并查集
查看>>
instanceof
查看>>
《深入分析Java Web技术内幕》读书笔记之JVM内存管理
查看>>
python之GIL release (I/O open(file) socket time.sleep)
查看>>
2015/8/4 告别飞思卡尔,抛下包袱上路
查看>>
软件开发与模型
查看>>
161017、SQL必备知识点
查看>>