两种方法做：优先队列和SBT。

先说说SBT吧。。。。

/************************************************* 题目大意： 针对每次查询，输出第K大数;算法思想：(1)根据题意可知,只需保留前K个大数，并且按降序排列; 也就是说每加入一个数就找到这个数的位置; 然后将大于K个元素之外的数删除; 利用优先级队列就可以很好的做到;(2)SBT或者树状数组解决; **************************************************/ #include<iostream> #include<algorithm> #include<cmath> #include<cstdio> using namespace std;const int N=1000010; int l[N],r[N],s[N]; int key[N]; int node;void left_rotate(int &t) {int k=r[t];r[t]=l[k];l[k]=t;s[k]=s[t];s[t]=s[l[t]]+s[r[t]]+1;t=k; }void right_rotate(int &t) {int k=l[t];l[t]=r[k];r[k]=t;s[k]=s[t];s[t]=s[l[t]]+s[r[t]]+1;t=k; }void maintain(int &t,bool flag) {if(flag==false){if(s[l[l[t]]]>s[r[t]])right_rotate(t);else if(s[l[r[t]]]>s[r[t]]){left_rotate(t);right_rotate(t);}elsereturn ;}else{if(s[r[r[t]]]>s[l[t]])left_rotate(t);else if(s[r[l[t]]]>s[l[t]]){right_rotate(t);left_rotate(t);}elsereturn ;}maintain(l[t],false);maintain(r[t],true);maintain(t,false);maintain(t,true); }void insert(int &t,int k) {if(!t){s[t=++node]=1;l[t]=r[t]=0;key[t]=k;}else{++s[t];if(key[t]>k)insert(l[t],k);elseinsert(r[t],k);maintain(t,k>=key[t]);} }int select(int t,int k) {int v=s[l[t]]+1;if(k==v)return key[t];else if(k<v)return select(l[t],k);elsereturn select(r[t],k-v); }int main() {int n,k;while(~scanf("%d%d",&n,&k)){int u=node=s[0]=0;while(n--){char c;int x;scanf(" %c",&c);if(c=='I'){scanf("%d",&x);insert(u,x);}elseprintf("%d\n",select(u,s[u]+1-k));}}return 0; }

然后优先队列也可以：

#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<queue> using namespace std;int main() {int n,k;while(~scanf("%d%d",&n,&k)){priority_queue<int,vector<int>,greater<int> > Q;for(int i=1;i<=n;i++){char c;scanf(" %c",&c);if(c=='I'){int x;scanf("%d",&x);Q.push(x);if(Q.size()>k)Q.pop();}elseprintf("%d\n",Q.top());}}return 0; }

 

 

总结

以上是生活随笔为你收集整理的HDU4006(The kth great number)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。