Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

這台機器有三顆功能鍵跟數字小鍵盤

功能鈕上分別寫著

1. Insert

2. Query MAX

3. Query MIN

旁邊寫著一行粗字: 極值經查詢後將會刪除 

題目看到這各位也明瞭了吧

請你寫出這台機器的程式

可以插入數字並且查詢其中的最大值與最小值 

1 3
1 100
2
1 4
3

100
3

×　example編輯

???? | ???? (管理：morris1028)


實作演算法 : Deap
估計min-max heap也行得通

功能都是在記憶體N的情況下，同時提供
Fetch max/min O(1)
Delete max/min O(lgN)
Insert O(lgN)

/**********************************************************************************/
/*  Problem: a091 "今晚打老虎" from ???? | ????                              */
/*  Language: C                                                                   */
/*  Result: AC (464ms, 1048KB) on ZeroJudge                                       */
/*  Author: morris1028 at 2011-04-06 22:14:20                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
struct Deap{
    int V;
}Deap[1000001], T;
int L=1;
 
int Judge(int p) {
    while(p > 3)    p/=2;
    return p; /*2 left-min heap 3 right-max heap*/
}
int MinPartner(int p) {
    int i=p, s=1;
    while(p > 3)    p/=2, s*=2;
    return i-s;
}
int MaxPartner(int p) {
    if(p == 2) return 2;
    int i=p, s=1;
    while(p > 3)    p/=2, s*=2;
    if(i+s > L) return (i+s)/2;
    return i+s;
}
void MinInsert(int S, int N) {
    int P=S/2;
    while(P > 1 && Deap[P].V > N)   Deap[S].V=Deap[P].V, S=P, P=S/2;
    Deap[S].V=N;
}
void MaxInsert(int S, int N) {
    int P=S/2;
    while(P > 1 && Deap[P].V < N)   Deap[S].V=Deap[P].V, S=P, P=S/2;
    Deap[S].V=N;
}
void Deap_Insert(int N) {
    L++;
    if(L==2) {
        Deap[2].V=N;
        return;
    }
    int p=L, i;
    switch( Judge(p) ) {
            case 3:/*right */
                i=MinPartner(p);
                if(N < Deap[i].V)     Deap[p].V=Deap[i].V, MinInsert(i, N);
                else MaxInsert(p, N);
                break;
            case 2:/*left */
                i=MaxPartner(p);
                if(N > Deap[i].V)     Deap[p].V=Deap[i].V, MaxInsert(i, N);
                else MinInsert(p, N);
                break;
        }
}
void Delete_Max()
{
    int p=L, t=Deap[L--].V, a, b, i;
    for(a = 3; a*2 <= L; a = b) {
            a*=2;
            if(a < L && Deap[a].V < Deap[a+1].V)      b=a+1;
            else b=a;
            Deap[a/2].V=Deap[b].V;
        }
       
    i= MinPartner(a);
    int biggest=i;
    if(2*i <= L) {
            biggest=2*i;
            if (((2*i + 1)<=L) && (Deap[2*i].V < Deap[2*i+1].V))
                biggest++;
        }
    if(t < Deap[biggest].V) {
            Deap[a].V=Deap[biggest].V;
            MinInsert(biggest, t);
        }
    else MaxInsert(a, t);
}
void Delete_Min()
{
    int p=L, t=Deap[L--].V, a, b, i;
    for(a = 2; a*2<=L; a = b) {
            a*=2;
            if(a < L && Deap[a].V > Deap[a+1].V)
                b=a+1;
            else b=a;
            Deap[a/2].V=Deap[b].V;
        }
    i= MaxPartner(a);
    if(t > Deap[i].V) {
            Deap[a]=Deap[i];
            MaxInsert(i, t);
        }
    else MinInsert(a, t);
}
main() {
    static int D, N, a;
    while(scanf("%d",&D)==1) {
            switch(D) {
                    case 1:scanf("%d",&N), Deap_Insert(N);break;
                    case 2:printf("%d\n", (L==2) ? Deap[2].V : Deap[3].V );
                            if(L==2) Delete_Min();
                            else Delete_Max();break;
                    case 3:printf("%d\n", Deap[2].V), Delete_Min();break;
                }
        }
    return 0;
}