hdu 4006 输入新数后输出第k大的数 set以及优先队列2中做法
The kth great numberTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 3775 Accepted Submission(s): 1583
Problem DescriptionInputOutputSample InputSample Output123HintXiao 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).题意：I m添加数 mQ 询问第 k大的数思路 ：set 控制集合的大小为k或者用优先队列#include<iostream>#include<cstdio>#include<queue>#include<vector>using namespace std;struct cmp{ bool operator()(int a,int b) { return a>b; }};priority_queue<int,vector<int>,cmp> q;int main(){ int n,k,p; char s[3]; while(scanf("%d%d",&n,&k)!=EOF) { while(!q.empty())q.pop(); while(n--) { scanf("%s",s); if(s[0]=='I') { scanf("%d",&p); q.push(p); if(q.size()>k)q.pop(); } else { printf("%d\n",q.top()); } } } return 0;}
#include<iostream>#include<cstdio>#include<queue>#include<vector>using namespace std;struct cmp{ bool operator()(int a,int b) { return a>b; }};priority_queue<int,vector<int>,cmp> q;int main(){ int n,k,p; char s[3]; while(scanf("%d%d",&n,&k)!=EOF) { while(!q.empty())q.pop(); while(n--) { scanf("%s",s); if(s[0]=='I') { scanf("%d",&p); q.push(p); if(q.size()>k)q.pop(); } else { printf("%d\n",q.top()); } } } return 0;}