Link：http://acm.hdu.edu.cn/showproblem.php?pid=4006
The kth great number Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 7134????Accepted Submission(s): 2916
Problem Description
Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number,or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming is too much,Xiao Bao is feeling giddy. Now,try to help Xiao Bao.
?
Input
There are several test cases. For each test case,the first line of input contains two positive integer n,k. Then n lines follow. If Xiao Ming choose to write down a number,there will be an " I" followed by a number that Xiao Ming will write down. If Xiao Ming choose to ask Xiao Bao,there will be a "Q",then you need to output the kth great number.?
?
Output
The output consists of one integer representing the largest number of islands that all lie on one line.?
?
Sample Input
8 3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q
?
Sample Output
1
2
3
Hint
Xiao Ming won't ask Xiao Bao the kth great number when the number of the written number is smaller than k. (1=<k<=n<=1000000).
?
Source
The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest
?
Recommend
lcy???|???We have carefully selected several similar problems for you:??
4003?
4007?
4004?
4008?
4005?
?
Statistic?|?
Submit?|?
Discuss?|?
Note
|
|
|
题意:题目会给出n个数,求第k大的数.
输入:第一行输入两个整数n 和 k
接下来有n行数据,输入的数据分为两种.
输入I 和 一个数字x?? 表示写入数字x
输入Q 表示进行一次询问 询问当前第k大的数是多少并输出这个数.
?
?开始使用sort进行排序,提交后会超时.
后来改用优先队列.
声明一个结构体
struct Node
{
int x;
friend bool operator < (Node a,Node b)
{
return a.x > b.x;
}
};
主要用于重载小于号,让小的优先.
输入时先输入k个数,输入k个数后再输入时需要判断输入的数与队头的大小关系.
输入数小于队头则不进队.
输入数大于队头则进队,弹出队头.
保证优先队列中只有k的元素.
而队头是k个元素中最小的元素.
即第k大元素
AC ?code：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
struct node{
int v;
friend bool operator < (node a,node b)
{
return a.v>b.v;
}
};
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
int cnt=0;
priority_queue<node>pq;
while(n--)
{
char c;
cin>>c;
if(c=='I')
{
if(cnt<k)
{
node t;
scanf("%d",&t.v);
pq.push(t);
cnt++;
}
else
{
node t;
scanf("%d",&t.v);
if(pq.top().v<t.v)
{
pq.pop();
pq.push(t);
}
}
}
else
{
if(c=='Q')
{
printf("%dn",pq.top().v);
}
}
}
}
return 0;
}
以下树状数组代码参考：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
const int N=1000005;
int cal[N],ptr[N];
struct TNode {
char c[5];
int m;
}node[N];
int n,m;
int lowbit(int x) {return x&-x;}
int getsum(int x) {
int s=0;
for(;x>0;s+=cal[x],x-=lowbit(x));
return s;
}
void update(int x,int value) {
for(;x<m;cal[x]+=value,x+=lowbit(x));
}
//数组中一共有m个数
int seach(int value) {
int l=1,r=m-1,mid;
while(l<=r)
{
mid=(l+r)>>1;
int t=ptr[mid];
if(t==value) return mid;
else if(t>value)
r=mid-1;
else l=mid+1;
}
return -1;
}
int find(int k) {
int cnt=0,sum=0;
for (int i=20;i>=0;i--) {
sum+=(1<<i);
if(sum>=m||cnt+cal[sum]>=k)
sum-=(1<<i);
else cnt+=cal[sum];
}
return sum+1;
}
int main() {
int i,j,k,t;
char le[5];
while(~scanf("%d%d",&k))
{
memset(cal,sizeof(cal));
for(i=1,m=1;i<=n;i++)
{
scanf("%s",node[i].c);
if(node[i].c[0]=='I')
{
scanf("%d",&node[i].m);
ptr[m++]=node[i].m;
}
}
//相当于离散化处理
sort(ptr+1,ptr+m);
//去重
for(i=2,j=1;i<m;i++)
{
if(ptr[i]!=ptr[j])
ptr[++j]=ptr[i];
}
m=j+1;
for(i=1,j=0;i<=n;i++)
{
if(node[i].c[0]=='I')
{
t=seach(node[i].m);
update(t,1); j++;
}
else
{
t=find(j+1-k);
printf("%dn",ptr[t]);
}
}
}
return 0;
}
附上别人其他做法（来自：http://blog.sina.com.cn/s/blog_732dd9320100trmj.html）：
SBT解法：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace?std;
const?int?N=1000005;
struct?TNode?{
????int?left,right,size,key;
????void?init() {
????????left=0;?right=0;?size=1;
????}
}node[N];
int?n,m,tot,root;
void?leftrorate(int?&t) {//左旋
????int?k=node[t].right;
????node[t].right=node[k].left;
????node[k].left=t;
????node[k].size=node[t].size;
????node[t].size=node[node[t].left].size+node[node[t].right].size+1;
????t=k;
}
void?rightrorate(int?&t) {//右旋
????int?k=node[t].left;
????node[t].left=node[k].right;
????node[k].right=t;
????node[k].size=node[t].size;
????node[t].size=node[node[t].left].size+node[node[t].right].size+1;
????t=k;
}
void?maintain(int?&t,bool?flag) {//维护
????if(!flag) {
????????if(node[node[node[t].left].left].size>node[node[t].right].size)
????????????rightrorate(t);
????????else if(node[node[node[t].left].right].size>node[node[t].right].size) {
????????????leftrorate(node[t].left);
????????????rightrorate(t);
????????}
????????else return?;
????}
????else?{
????????if(node[node[node[t].right].right].size>node[node[t].left].size)
????????????leftrorate(t);
????????else if(node[node[node[t].right].left].size>node[node[t].left].size) {
????????????rightrorate(node[t].right);
????????????leftrorate(t);
????????}
????????else return?;
????}
????maintain(node[t].left,0);
????maintain(node[t].right,1);
????maintain(t,0);
????maintain(t,1);
}
void?insert(int?&t,int?value) {//插入
????if(!t) {
????????t=++tot;
????????node[t].init();
????????node[t].key=value;
????}
????else?{
????????node[t].size++;
????????if(value<node[t].key)?insert(node[t].left,value);
????????else?insert(node[t].right,value);
????????maintain(t,value>=node[t].key);
????}
}
int?find(int?t,int?k) {//查找第k小的数
????if(k<=node[node[t].left].size)?return?find(node[t].left,k);
????else if(k>node[node[t].left].size+1)
????????return?find(node[t].right,k-node[node[t].left].size-1);
????else return?node[t].key;
}
int?main() {
????int?k,end;
????char?le[5];
????while(~scanf("%d%d",&n,&end)) {
????????root=tot=0;
????????for(k=0;k<n;k++) {
????????????scanf("%s",le);
????????????switch(le[0]) {
????????????case?'I':scanf("%d",&m);
????????????????insert(root,m);?break;
????????????default?:
????????????????printf("%dn",find(root,tot+1-end));
????????????}
????????}
????}
????return?0;
}
树状数组解法：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace?std;
const?int?N=1000005;
int?cal[N],ptr[N];
struct?TNode?{
????char?c[5];
????int?m;
}node[N];
int?n,m;
int?lowbit(int?x) {return?x&-x;}
int?getsum(int?x) {
????int?s=0;
????for(;x>0;s+=cal[x],x-=lowbit(x));
????return?s;
}
void?update(int?x,int?value) {
????for(;x<m;cal[x]+=value,x+=lowbit(x));
}
int?seach(int?value) {
????int?l=1,r=m-1,mid;
????while(l<=r) {
????????mid=(l+r)>>1;
????????int?t=ptr[mid];
????????if(t==value)?return?mid;
????????else if(t>value)?r=mid-1;
????????else?l=mid+1;
????}
????return?-1;
}
int?find(int?k) {
????int?cnt=0,sum=0;
????for?(int?i=20;i>=0;i--) {
????????sum+=(1<<i);
????????if(sum>=m||cnt+cal[sum]>=k)
????????????sum-=(1<<i);
????????else?cnt+=cal[sum];
????}
????return?sum+1;
}
int?main() {
????int?i,j,k,t;
????char?le[5];
????while(~scanf("%d%d",&k)) {
????????memset(cal,0,sizeof(cal));
????????for(i=1,m=1;i<=n;i++) {
????????????scanf("%s",node[i].c);
????????????if(node[i].c[0]=='I') {
????????????????scanf("%d",&node[i].m);
????????????????ptr[m++]=node[i].m;
????????????}
????????}
????????sort(ptr+1,ptr+m);
????????for(i=2,j=1;i<m;i++) {
????????????if(ptr[i]!=ptr[j])?ptr[++j]=ptr[i];
????????}
????????m=j+1;
????????for(i=1,j=0;i<=n;i++) {
????????????if(node[i].c[0]=='I') {
????????????????t=seach(node[i].m);
????????????????update(t,1);?j++;
????????????}
????????????else?{
????????????????t=find(j+1-k);
????????????????printf("%dn",ptr[t]);
????????????}
????????}
????}
????return?0; }
