hdu 4006 The kth great number(线段树 || 优先队列)

本文主要是介绍hdu 4006 The kth great number(线段树 || 优先队列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4006

求一个数字序列的第K大的值。先输入两个数字n,k,接着是n行输入，I表示加入新的数字，Q是询问第k大的数字。

Sample Input

  8 3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q

Sample Output

  1
2
3

练习线段树遇到这道题的，听说方法还挺多的。
线段树：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e6+5; //',INF=0x3f3f3f3f;
int ans[maxn];
struct node{int l,r,count;int mid(){  return (l+r)/2; }int length(){  return (r-l+1); }
}tree[maxn<<2];
void build(int a,int b,int root){tree[root].l=a;tree[root].r=b;tree[root].count=0;if(a==b){return ;}int m=tree[root].mid();build(a,m,2*root);build(m+1,b,2*root+1);
}
void insert(int root,int number){if(tree[root].l==tree[root].r){tree[root].count++;return ;}if(number<=tree[root].mid()) insert(2*root,number);else insert(2*root+1,number); // number-tree[2*root].count is wrongtree[root].count=tree[2*root].count+tree[2*root+1].count;
}
int query(int root,int number){if(tree[root].l==tree[root].r){return tree[root].l;}int ans;if(number<=tree[2*root].count)ans=query(2*root,number);else ans=query(2*root+1,number-tree[2*root].count);  //we need "number-tree[2*root].count"return ans;
}
int main()
{//freopen("cin.txt","r",stdin);int n,k;while(cin>>n>>k){build(1,maxn,1);char str[3];int top=0;for(int i=0;i<n;i++){scanf("%s",str);if(str[0]=='I'){int a;scanf("%d",&a);insert(1,a);top++;}else {printf("%d\n",query(1,top-k+1));}}}return 0;
}

优先队列：
第一次写好的代码怀着忐忑的心情交上去，没错，果然超时了：

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=1e6+5;
int number[maxn];
int main()
{//freopen("cin.txt","r",stdin);int n,k;while(cin>>n>>k){priority_queue<int> que;char s[3];for(int i=0;i<n;i++){scanf("%s",s);if(s[0]=='I'){int a;scanf("%d",&a);que.push(a);}else {int j;for(j=0;j<k;j++){number[j]=que.top();que.pop();}printf("%d\n",number[j-1]);for(j=0;j<k;j++){que.push(number[j]);}}}}return 0;
}

想个办法把第二个循环去掉吧，抓住主要矛盾，忽略次要因素：

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
const int maxn=1e6+5;
int number[maxn];
int main()
{//freopen("cin.txt","r",stdin);int n,k;while(cin>>n>>k){priority_queue<int,vector<int>,greater<int> > que;  //从小到大char s[3];for(int i=0;i<n;i++){scanf("%s",s);if(s[0]=='I'){int a;scanf("%d",&a);que.push(a);if(que.size()>k)que.pop();}else {printf("%d\n",que.top());}}}return 0;
}

记住要用functional头文件，不然会Compilation Error。

这篇关于hdu 4006 The kth great number(线段树 || 优先队列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！