The kth great number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 6637 Accepted Submission(s): 2671
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
HintXiao Ming won't ask Xiao Bao the kth great number when the number of the written number is smaller than k. (1=
Source
The
36th ACM/ICPC Asia Regional Dalian Site ―― Online Contest
这道可以直接就用STL的优先队列水过，最近要熟悉stl里面的操作和用法，用这些题练练手，还是不错的，这道题要注意的是用stl的优先队列时，元素的比较规则默认是按元素值的大小从大到小排序；这道题用优先队列来做的话，直接是维护一个k长度的优先队列，要把元素值大小从小到大排序，它的第k大的值就是队首元素，所以每次的查询就输出队首元素就行了；这里就需要重载操作符来实现它的排序；
下面是用stl写的代码；
#include
#include
using namespace std; int main() { int n,k,m; char s[5]; while(scanf("%d%d",&n,&k)!=EOF) { priority_queue
, greater
> q;//这里就是对优先队列进行排序 for(int i=0;i
q.top()) { q.pop();//出队 q.push(m); } } else { printf("%d\n",q.top());//输出 } } } return 0; }
这道题还可以用其他方法做，在网上还看到了其他方法，用SBT也可以做，也是一种平衡二叉树，这里学习一下这种写法，可以用作以后的模板；
- 数据结构：
- SBT(Size Balanced Tree),又称傻逼树;
-
- 数据域：
- 值域key,左孩子left,右孩子right,保持平衡的size;
-
- 性质：
- 每棵子树的大小不小于其兄弟的子树大小;
-
- 插入：
- 插入算法先简单插入节点，然后调用一个维护过程以保持性质;
-
- 删除：
- 删除操作与普通维护size域的二叉查找树相同;
-
- 最大值和最小值：
- 由于SBT本身已经维护了size域;
- 所以只需用Select(T,1)来求最大值;
- Select(T,T.size)求最小值;
- 其中Select(T,k)函数返回树T在第k位置上的节点值; 下面是ac的代码；参考别人的；sbt还是有点不清楚啊；
#include
#include
#define MAX 1000010 int n,m; struct SBT {//结构体 int left,right,size,key; void Init() { left = right = 0; size = 1; } }a[MAX]; int tot,root; void left_rotate(int &t) {//左旋转 int k = a[t].right; a[t].right = a[k].left; a[k].left = t; a[k].size = a[t].size; a[t].size = a[a[t].left].size + a[a[t].right].size + 1; t = k; } void right_rotate(int &t) {//右旋转 int k = a[t].left; a[t].left = a[k].right; a[k].right = t; a[k].size = a[t].size; a[t].size = a[a[t].left].size + a[a[t].right].size + 1; t = k; } void maintain(int &t,int flag) {//维护 if (flag == 0) { if (a[a[a[t].left].left].size > a[a[t].right].size) right_rotate(t); else if (a[a[a[t].left].right].size > a[a[t].right].size) left_rotate(a[t].left),right_rotate(t); else return; } else { if (a[a[a[t].right].right].size > a[a[t].left].size) left_rotate(t); else if (a[a[a[t].right].left].size > a[a[t].left].size) right_rotate(a[t].right),left_rotate(t); else return; } maintain(a[t].left,0); maintain(a[t].right,1); maintain(t,0); maintain(t,1); } void insert(int &t,int v) {//插入 if (t == 0) t = ++tot,a[t].Init(),a[t].key = v; else { a[t].size++; if (v < a[t].key) insert(a[t].left,v); else insert(a[t].right,v); maintain(t,v>=a[t].key); } } int del(int &t,int v) {//删除 if (!t) return 0; a[t].size--; if (v == a[t].key || v < a[t].key && !a[t].left || v > a[t].key && !a[t].right) { if (a[t].left && a[t].right) { int p = del(a[t].left,v+1); a[t].key = a[p].key; return p; } else { int p = t; t = a[t].left + a[t].right; return p; } } els