hdu 4006 The kth great number （優先隊列+STB+最小堆）
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;iq.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;
}
}
else return del(v a[a[t].left].size + 1)
return find(a[t].right,k-a[a[t].left].size-1);
return a[t].key;
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m) != EOF) {
tot = root = 0;
char ope[10];
while (n--) {
scanf("%s",ope);
if (ope[0] == 'I') {
scanf("%d",&k);
insert(root,k);
}
else printf("%d\n",find(root,a[root].size+1-m));
}
}
}
http://www.nocow.cn/index.php/Size_Balanced_Tree這裡面SBT講的還不錯，自己還是要多看幾遍，還沒完全弄懂
http://blog.csdn.net/jarily/article/details/8679236 這個博客也是講SBT的
http://blog.csdn.net/acceptedxukai/article/details/6921334
這個題目看到別人用了線段樹來做；線段樹每個節點保存當前編號的數出現的次數。每次查詢從小到大第N-K+1個數（N為當前數的總數）。
貼上別人的代碼；學習一下；
#include
#include
#include
using namespace std;
#define MAXN 1001000
#define lson l,m,root<<1
#define rson m+1,r,root<<1|1
int n,k;
int node[MAXN<<2];
void push_up(int root)
{
node[root]=node[root<<1]+node[root<<1|1];
}
void build(int l,int r,int root)
{
if(l==r)
{
node[root]=0;
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
push_up(root);
}
void update(int n,int l,int r,int root)
{
if(l==r)
{
node[root]++;
return ;
}
int m=(l+r)>>1;
if(n<=m)
update(n,lson);
else
update(n,rson);
push_up(root);
}
int query(int p,int l,int r,int root)
{
if(l==r)
{
return l;
}
int m=(l+r)>>1;
int ret;
if(p<=node[root<<1])
ret=query(p,lson);
else
ret=query(p-node[root<<1],rson);
return ret;
}
void solve()
{
char a[5];
int ff;
build(1,MAXN,1);
int counts=0;
for(int i=1;i<=n;i++)
{
scanf("%s",a);
if(a[0]=='I')
{
scanf("%d",&ff);
update(ff,1,MAXN,1);
counts++;
}
else
printf("%d\n",query(counts-k+1,1,MAXN,1));
}
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
solve();
return 0;
}
還有人用了treap樹，那個和SBT類似；
這道題主要還是練一下最小堆；
對最小堆還不是很熟悉，還是要多練；可以當做自己的模板來使用
#include
#include
#include
using namespace std;
int heap[1000010],size;
void down(int r)//往下交換
{
while(rheap[son+1]?son+1:son;
if(son<=size && heap[r]>heap[son]) swap(heap[r],heap[son]);
else return;
r=son;
}
}
void up(int r)//往上交換，查詢
{
while(r!=1)
{
if(heap[r]>=1;
}
}
void heap_push(int k)//入隊
{
heap[++size]=k;
up(size);
}
void heap_pop()//出隊
{
heap[1]=heap[size--];
down(1);
}
int main()
{
int n,k,m;
char s[5];
while(scanf("%d%d",&n,&k)!=EOF)
{
size=0;
for(int i=0;ik) heap_pop();
}
else
{
printf("%d\n",heap[1]);
}
}
}
return 0;
}
用堆來模擬優先隊列。
