The kth great number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 16226 Accepted Submission(s): 6110
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). 题意:输入I表示插入一个数,输入Q表示要你求第k大的数 题解:用multiset,会自动排序,但是不会去重
#include<iostream> #include<algorithm> #include<string.h> #include<string> #include<math.h> #include<map> #include<set> #define ll long long using namespace std; multiset<ll>p; string s,ss; int n,k; ll x; int main() { char c; while(cin>>n>>k) { p.clear(); for(int i=0;i<n;i++) { cin>>c; if(c=='I') { cin>>x; p.insert(x); if(p.size()>k) p.erase(p.begin()); } else { multiset<ll>::iterator it; it=p.begin(); cout<<*it<<endl; } } } return 0; }