50233. Max-heap
難度：4/5
看到RE就先把陣列開三倍大再說。因為今天初始化的時候\(N <= 10^6\)，每筆query可以增加一個element，所以上限開要到\(N + M = 3 \times 10 ^6\)。
然後也是照著刻就好，但沒修過DSA的人肯定會發瘋。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#define max(a,b) ((a)>(b)?(a):(b))
// #define min(a,b) ((a)<(b)?(a):(b))
#define left(n) (2 * (n))
#define right(n) (2 * (n) + 1)
#define parent(n) ((n) / 2)
typedef struct{
int arr[3000000];
int n;
} s_heap;
static inline void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
int get_largest(s_heap* h, int i){
int l = left(i), r = right(i);
int largest;
if(l <= h->n && h->arr[l] > h->arr[i]){
largest = l;
}
else{
largest = i;
}
if(r <= h->n && h->arr[r] > h->arr[largest]){
largest = r;
}
return largest;
}
void max_heapify(s_heap* h, int i){
int largest = get_largest(h, i);
while(largest != i){
swap(&(h->arr[i]), &(h->arr[largest]));
i = largest;
largest = get_largest(h, i);
}
}
void build_max_heap(s_heap* h){
for(int i = (h->n / 2); i >= 1; i--){
max_heapify(h, i);
}
}
int extract_max(s_heap* h){
if(h->n < 1) return -1;
else{
int max_num = h->arr[1];
h->arr[1] = h->arr[h->n];
h->n -= 1;
max_heapify(h, 1);
return max_num;
}
}
int insert(s_heap* h, int key){
h->n += 1;
int i = h->n;
h->arr[i] = key;
while(i > 1 && h->arr[parent(i)] < h->arr[i]){
swap(&(h->arr[i]), &(h->arr[parent(i)]));
i = parent(i);
}
}
int main(){
s_heap* h = (s_heap*) malloc(sizeof(s_heap));
scanf("%d", &h->n);
for(int i = 1; i <= h->n; i++) scanf("%d", &h->arr[i]);
build_max_heap(h);
for(int i = 1; i <= h->n; i++) printf("%d ", h->arr[i]);
printf("\n");
int m; scanf("%d", &m);
while(m--){
int q; scanf("%d", &q);
if(q == -1){
int rtv = extract_max(h);
printf("%d ", rtv);
}
else{
insert(h, q);
}
}
}