?? 北大oj 3481 c++源代碼.cpp
字號:
#include<stdio.h>
#define MAXSIZE 1000000
typedef struct{
long id;
long prior;
} elem;
typedef struct{
elem order[MAXSIZE];
long length;
} Client;
void MAX_HEAPIFY(Client &a, int i)
{
long largest, l, r;
elem temp;
l = 2*i;
r = 2*i + 1;
if(l <= a.length && a.order[i].prior < a.order[l].prior) {
largest = l;
} else {
largest = i;
}
if(r <= a.length && a.order[largest].prior < a.order[r].prior) {
largest = r;
}
if(i != largest) {
temp = a.order[i];
a.order[i] = a.order[largest];
a.order[largest] = temp;
MAX_HEAPIFY(a, largest);
}
}
void BUILD_MAX_HEAP(Client &a)
{
int i;
for(i = a.length/2; i > 0; i --) {
MAX_HEAPIFY(a, i);
}
}
void HEAP_EXTRACT_MAX(Client &a)
{
if(a.length < 1) {
printf("0\n");
} else {
a.order[0] = a.order[1];
a.order[1] = a.order[a.length];
a.length --;
MAX_HEAPIFY(a, 1);
printf("%ld\n", a.order[0].id);
}
}
void INCREASE_KEY(Client &a, long i, long key)
{
elem temp;
a.order[i].prior = key;
while(i > 1 && a.order[i].prior > a.order[i/2].prior) {
temp = a.order[i];
a.order[i] = a.order[i/2];
a.order[i/2] = temp;
i /= 2;
}
}
void Insertion(Client &a, elem nelem)
{
a.length ++;
a.order[a.length] = nelem;
INCREASE_KEY(a, a.length, a.order[a.length].prior);
}
int main(void)
{
int command;
long max, i;
Client L;
elem temp;
L.length = 0;
scanf("%d", &command);
while(command != 0) {
switch(command) {
case 1:
scanf("%ld%ld", &temp.id, &temp.prior);
Insertion(L, temp);
break;
case 2:
HEAP_EXTRACT_MAX(L);
break;
case 3:
for(i = L.length/2 + 2, max = L.length/2 + 1; i <= L.length; i++) {
if(L.order[i].prior < L.order[max].prior) {
max = i;
}
}
INCREASE_KEY(L, max, L.order[1].prior + 1);
HEAP_EXTRACT_MAX(L);
break;
}
scanf("%d", &command);
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -