首页 > 代码库 > HDU 4006

HDU 4006

2024-07-14 21:44:43   239人阅读

题目大意：

给定一系列的数，并能够不断往里添加数使这个序列得到更新，问第k大的数是几

 

这里可以用两种方法来做：
1.运用优先队列将其由小到大保存，令队列里的数据始终只有k个，那么队首元素就是最小值

2.运用堆排列，同样也只是在堆中存放k个元素，将最小值的位置放在堆顶，当超过k个的元素加入时，如果加入的数大于堆顶位置对应的元素，那么将那个数位置上的数更新掉并重排堆，如果小于就不管它了。

 

优先队列

 1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6  7 int main() 8 { 9     int n,k,x;10     char c;11     while(scanf("%d%d",&n,&k)!=EOF){12         priority_queue<int,vector<int>,greater<int> > q;13         for(int i=0;i<n;i++){14             cin>>c;15             if(c==‘I‘){16                 scanf("%d",&x);17                 q.push(x);18                 int len=q.size();19                 if(len>k) q.pop();20             }21             else printf("%d\n",q.top());22         }23     }24     return 0;25 }
View Code

 但我用堆排列时不知道为什么一直报错T T，果然还是太渣了吗？！我在此先存放这代码，以后在做研究

堆排列

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define INF 0x3f3f3f3f 7 #define N 1000100 8 int a[N],tree[4*N],D; 9 10 void update(int i)11 {12     for(;i^1;i>>=1)13         tree[i>>1]=a[tree[i]]>a[tree[i^1]]?tree[i^1]:tree[i];14 }15 16 int main()17 {18     int n,k,x,cnt;19     char c;20     while(scanf("%d%d",&n,&k)!=EOF){21         cnt=0;22         for(D=1;D<k+2;D<<=1);23         for(int i=0;i<=D;i++) a[i]=N;24         memset(tree,0,sizeof(tree[0])*(D*2));25         for(int i=0;i<D;i++) tree[D+i]=i;26         for(int i=D-1;i>=1;i--) tree[i]=a[tree[i<<1]]<a[tree[i<<1|1]]?tree[i<<1]:tree[i<<1|1];27         for(int i=0;i<n;i++)28         {29             cin>>c;30             if(c==‘I‘){31                 cnt++;32                 scanf("%d",&x);33                 if(cnt>k){34                     if(x>tree[1]){35                         a[tree[1]]=x;36                         update(D+tree[1]);37                     }38                 }39                 else{40                     a[cnt]=x;41                     update(D+cnt);42                 }43             }44             else45                 printf("%d\n",a[tree[1]]);46         }47     }48     return 0;49 }
View Code

 


联系
我们