[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<<' ';
}
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();
}
}
[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;
}
}
}