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

比眉伴天荒 2022-08-02 09:52 146阅读 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 条评论，146人围观）

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

相关阅读

相关 UVA1045 The Great Wall Game

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

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

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

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

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

相关 c++stl和std_C ++ STL多集容器– std :: multiset

![7cb3a601c4bf448d05a623805a35b8d8.png][] c++stl和std In this tutorial you will learn a

落日映苍穹つ/ 2022年12月07日 13:53/ 0 赞/ 185 阅读

相关 STL源码：multimap、multiset

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

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

相关 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 赞/ 147 阅读

相关 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 赞/ 171 阅读

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

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

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

相关树的重心 Shaass the Great

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

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

相关 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 赞/ 179 阅读

相关 C++进阶STL-set、multiset容器

set、multiset容器 set和multiset基于红黑树，自动排序 set中元素不可以重复，multiset中元素可以重复，都在<set>头文件中

淩亂°似流年/ 2022年05月09日 07:14/ 0 赞/ 275 阅读