The kth great number(C++ stl multiset的应用)

比眉伴天荒 2022-08-02 09:52 160阅读 0赞

# The kth great number #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)  
Total Submission(s): 8117    Accepted Submission(s): 3215**

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).

**multiset就是允许里面有多个重复元素！set是不允许的，你可能**

**又问了，允许重复的set容器跟数组不是没有区别了吗？在排序**

**方面，multiset是插入即排序，这样就很方便了，然而你用**

**vector每次插入一个还需要重新排序，这样就有点麻烦了！**

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 STL之multiset（可重集）

[https://www.cnblogs.com/tvtaqa/p/7128584.html ][https_www.cnblogs.com_tvtaqa_p_712858

ゝ一世哀愁。/ 2023年08月17日 16:26/ 0 赞/ 104 阅读

相关 UVA1045 The Great Wall Game

题目链接：[UVA1045 The Great Wall Game][] 题目大意：在一个n\n的棋盘上有n个棋子，要求通过移动棋子使棋子的排布满足以下情况之一：呈横行排列

约定不等于承诺〃/ 2023年08月17日 15:35/ 0 赞/ 127 阅读

相关 C++(STL):34--- multiset容器详解

前面章节中，对 set 容器做了详细的讲解。回忆一下，set 容器具有以下几个特性：不再以键值对的方式存储数据，因为 set 容器专门用于存储键和值相等的键值对，因此

以你之姓@/ 2022年12月29日 09:52/ 0 赞/ 200 阅读

相关 Hdu 4006 The kth great number (第k大元素优先队列的几种写法)

题意：不断地读入数据，询问第k大的是多少。思路：维护只有k个元素且队首元素最小的优先队列总结下常用的三种写法，个人还是喜欢结构体这种。 include<cst

阳光穿透心脏的1/2处/ 2022年08月25日 01:43/ 0 赞/ 12 阅读

相关 STL源码：multimap、multiset

multiset和multimap与set、map的特性以及用法完全相同，差别之一是它允许一个键对应多个实例，因为它们的插入操作使用的是底层RB-tree的insert\_eq

刺骨的言语ヽ痛彻心扉/ 2022年08月07日 10:45/ 0 赞/ 203 阅读

相关 The kth great number(C++ stl multiset的应用)

The kth great number Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65

比眉伴天荒/ 2022年08月02日 09:52/ 0 赞/ 161 阅读

相关 The kth great number（优先队列）

The kth great number Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65

超、凢脫俗/ 2022年08月02日 09:52/ 0 赞/ 184 阅读

相关【STL】set和multiset的初步认知

set/multiset是一个集合容器，我们可以对这个容器进行插入，删除，查找等工作。set的元素内容只有一个键值（key，key和value为同一个值），不允许重复冗余，当对

ゝ一纸荒年。/ 2022年07月15日 10:18/ 0 赞/ 209 阅读

相关树的重心 Shaass the Great

题目:[CodeForces - 294E][] 题意: 有一棵树，切断某条边之后，重造一条长度一样的边连接两个新子树，使得新子树所有点到所有点的距离和最小。

偏执的太偏执、/ 2022年06月14日 06:24/ 0 赞/ 197 阅读

相关 HDU4006 The kth great number————栈和队列（优先队列）

Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choos

╰半夏微凉°/ 2022年05月18日 01:43/ 0 赞/ 189 阅读