a091 - 今晚打老虎

Sylveon

原題：http://zerojudge.tw/ShowProblem?problemid=a091
AC：http://zerojudge.tw/Submissions?problemid=a091&account=lfs92002

SMMH的實作題，聽說可以用set來爆我還沒試過，不知道會不會TLE

[C++] 純文本查看 復制代碼

/**********************************************************************************/
/*  Problem: a091 "今晚打老虎" from Deap | min-max heap | double-ended heap  */
/*  Language: CPP (2601 Bytes)                          */
/*  Result: AC(0.8s, 4.2MB) judge by this@ZeroJudge                 */
/*  Author: lfs92002 at 2014-03-03 09:40:37                     */
/**********************************************************************************/


#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

#define ROOT 0
#define PA(X) (((X)-1)/2)
#define LC(X) ((X)*2+1)
#define RC(X) ((X)*2+2)
#define GP(X) PA(PA(X))

int heap[1000005];
int size=0;

void insert(int var)
{
    int pos=++size;
    heap[pos]=var;
    //step1
    if(pos%2==0) //is right-child
    {
        if(heap[pos-1]>heap[pos])
        {
            swap(heap[pos-1],heap[pos]);
            pos--;
        }
    }
    while(pos>2)
    {
        int pGL=LC(GP(pos));
        int pGR=RC(GP(pos));
        if(heap[pos]<heap[pGL])
        {
            swap(heap[pos],heap[pGL]);
            pos=pGL;
        }
        else if(heap[pGR]<heap[pos])
        {
            
            swap(heap[pos],heap[pGR]);
            pos=pGR;
        }
        else
        {
            break;
        }
    }
}
int pop_max()
{
    int M=heap[2],pos=2;
    heap[2]=heap[size--];
    while(pos<=size)
    {
        int pR=RC(pos);
        int pPR=RC(LC(PA(pos)));
        
        if(pR>size)pR=-1;
        if(pPR>size)pPR=-1;
        
        if(heap[pos-1]>heap[pos])
        {
            swap(heap[pos-1],heap[pos]);
            continue;
        }
        
        if(pR<0&&pPR<0)break;
        if(pR<0)
        {
            if(heap[pPR]>heap[pos])
            {
                swap(heap[pPR],heap[pos]);
                pos=pPR;
            }
            else
            {
                break;
            }
        }
        else
        {
            int C=(heap[pR]>heap[pPR])?pR:pPR;
            if(heap[C]>heap[pos])
            {
                swap(heap[C],heap[pos]);
                pos=C;
            }
            else
            {
                break;
            }
        }
    }
    if(heap[pos-1]>heap[pos])
    {
        swap(heap[pos-1],heap[pos]);
    }
    return M;
}

int pop_min()
{
    int m=heap[1],pos=1;
    heap[1]=heap[size--];
    while(pos<=size)
    {
        int pL=LC(pos);
        int pPL=LC(RC(PA(pos)));
        
        if(pL>size)pL=-1;
        if(pPL>size)pPL=-1;
        if(pos+1<=size)
        {
            if(heap[pos]>heap[pos+1])
            {
                swap(heap[pos],heap[pos+1]);
                continue;
            }
        }
        
        if(pL<0 &&pPL<0)break;
        if(pPL<0) //Only pL
        {
            if(heap[pL]<heap[pos])
            {
                swap(heap[pL],heap[pos]);
                pos=pL;
            }
            else
            {
                break;
            }
        }
        else
        {
            int C=(heap[pL]<heap[pPL])?pL:pPL;
            if(heap[C]<heap[pos])
            {
                swap(heap[C],heap[pos]);
                pos=C;
            }
            else
            {
                break;
            }
        }
    }
    if(pos+1<=size)
    {
        if(heap[pos]>heap[pos+1])
            swap(heap[pos],heap[pos+1]);
    }
    return m;
}
void show()
{
    cout<<"SMMH :";
    for(int i=1;i<=size;++i)
    {
        cout<<heap[i]<<' ';
    }
    cout<<endl;
}
int main()
{
    size=0;
    int id;
    while(~scanf("%d",&id))
    {
        if(id==1)
        {
            scanf("%d",&id);
            insert(id);
        }
        else if(size == 1) //only 1 obj
        {
            printf("%d\n",pop_min());
        }
        else if(id==2)
        {
            printf("%d\n",pop_max());
        }
        else
        {
            printf("%d\n",pop_min());
        }
    //    show();
    }
}

Sylveon

multiset版本，執行時間比較慢，但還是過了，才30多行的code沒天理啊！

[C++] 純文本查看 復制代碼

/**********************************************************************************/
/*  Problem: a091 "今晚打老虎" from Deap | min-max heap | double-ended heap  */
/*  Language: CPP (527 Bytes)                                                     */
/*  Result: AC(1s, 23.3MB) judge by this@ZeroJudge                                */
/*  Author: lfs92002 at 2014-05-09 08:36:42                                       */
/**********************************************************************************/


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;


int main()
{
        multiset<int> s;
        multiset<int>::iterator sit;
        multiset<int>::reverse_iterator srit;
        int D,t;
        while(~scanf("%d",&D)){
                switch(D){
                        case 1:
                                scanf("%d",&t);
                                s.insert(t);
                                break;
                        case 2:
                                srit=s.rbegin();
                                printf("%d\n",*srit);
                                s.erase((++srit).base());
                                break;
                        case 3:
                                sit=s.begin();
                                printf("%d\n",*sit);
                                s.erase(sit);
                                break;
                }
        }
}