hdu 1512 Monkey King 左式堆

缘起

【1】中学习了左式堆这种小巧的数据结构. 于是想找个板子题来测试一下这种数据结构的性能. 于是找到了hdu1512

分析

题意是（~我可耻的说，全部来自于Google翻译）

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
一旦进入森林，就会有N只攻击性的猴子。 一开始，他们每个人都以自己的方式做事，没有人互相认识。 但猴子无法避免争吵，而且只发生在彼此不认识的两只猴子之间。 当它发生时，两只猴子都会邀请他们中最强壮的朋友，并决斗。 当然，在决斗之后，两只猴子和所有朋友都互相认识，即使他们曾经发生冲突，上面的争吵也不再发生在这些猴子之间。

假设每个猴子都有一个强度值，在决斗后将减少到原来的一半（即10将减少到5，5将减少到2）。

我们还假设每只猴子都了解自己。 也就是说，当他是所有朋友中最强者时，他自己会去决斗。

【输入】
有几个测试用例，每个案例由两部分组成。

第一部分：第一行包含一个整数N（N <= 100,000），表示猴子的数量。 然后是N行。 每行有一个数字，表示第i个猴子的强度值（<= 32768）。

第二部分：第一行包含一个整数M（M <= 100,000），表示发生了M次冲突。 然后是M行，每行包含两个整数x和y，表示第X个猴子和第Y个之间存在冲突。

【输出】
对于每个冲突，如果两只猴子互相认识则输出-1，否则在决斗后输出最强猴子的强度值。

【样例输入】
5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5
【样例输出】
8
5
5
-1
10

但凡是求最强的，考虑堆结构. 而堆的实现无非 1.二叉堆 2. 左式堆.

使用哪一种，主要就是看有木有合并操作. 本题显然是有的. 所以当仁不让的使用左式堆. 而要判断两只猴子是否属于同一个堆，则显然需要引入并查集. 所以本题是 左式堆+并查集

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>

using namespace std;
//#define LOCAL
const int INF = 0x3f3f3f3f;
const int MAX_N = 100005;


typedef struct LeftHeapNode
{
	LeftHeapNode *left, *right;
	int data; 
	int npl; 
	LeftHeapNode(int data = 0):left(0), right(0), data(data),npl(0){}

}LeftHeapNode, *LeftHeap; 

int a[MAX_N];
LeftHeap b[MAX_N];
int f[MAX_N];

void swap(LeftHeap node)
{
	LeftHeap t = node->left;
	node->left = node->right;
	node->right = t;
}

LeftHeap merge(LeftHeap, LeftHeap);
LeftHeap merge1(LeftHeap, LeftHeap);


LeftHeap merge1(LeftHeap node1, LeftHeap node2) 
{
	if (!node1->left) node1->left = node2; 
	else
	{
		node1->right = merge(node1->right, node2); 
		if (node1->left->npl < node1->right->npl) swap(node1); 
		node1->npl = node1->right->npl + 1; 
	}
	return node1;
}


LeftHeap merge(LeftHeap root1, LeftHeap root2) 
{
	if (!root1) return root2;
	if (!root2) return root1;
	return root1->data > root2->data ? merge1(root1, root2): merge1(root2, root1);
}

int _max(LeftHeap root) {return root->data;}

LeftHeap insert(LeftHeap root, int data)
{
	LeftHeap node = new LeftHeapNode(data);
	return merge(root, node);
}

LeftHeap build(int *a, int n) 
{
	LeftHeap root = 0;
	for (int i = 0; i<n;i++) root = insert(root, a[i]);
	return root;
}

int pop(LeftHeap &root) 
{
	if (!root) return -INF; 
	int ret = root->data;
	root = merge(root->left, root->right); 
	return ret;
}

int getf(int i){return f[i]==i?i:f[i]=getf(f[i]);}

void merge(int i, int j) // 与【2】中给出的并查集合并略有不同，因为这里要求最大, 所以合并不能随意合并了, 我们希望的结果是 父节点总是那个群体中战斗力最强的那只猴子
{
	int f1 = getf(i); // i的爹, i朋友圈中的最强战力存在
	int f2 = getf(j); // j的爹, j朋友圈中的最强战力存在
	
	int strgegth1 = b[f1]->data/2; // 战力减半
	int strgegth2 = b[f2]->data/2;

	pop(b[f1]);
	b[f1] = insert(b[f1], strgegth1); // 重新加入战力减半的曾今之王
	
	pop(b[f2]);
	b[f2] = insert(b[f2], strgegth2);

	if (b[f1]->data > b[f2]->data) 
	{
		f[f2] = f1;// 则是f2并入f1
		b[f1]= merge(b[f1],b[f2]);
		printf("%d\n", b[f1]->data);
	}
	else
	{
		f[f1] = f2;// 则是f1并入f2
		b[f2] = merge(b[f1], b[f2]);
		printf("%d\n", b[f2]->data);
	}
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int n,m;
	while(~scanf("%d", &n))
	{
		for (int i = 1; i<=n;scanf("%d", a+i),b[i] = new LeftHeapNode(a[i]),f[i] = i, i++); // b[i]的new 初始化不要放在外面, 会MLE的. 
		scanf("%d", &m);
		int x,y;
		while(m--)
		{
			scanf("%d%d", &x, &y);
			if (getf(x)==getf(y)) puts("-1");
			else
			{
				merge(x,y);
			}
		}
	}
	return 0;
}

如果对于上面的代码有不明白的，参考【1】和【2】.

ac情况

Status Accepted
Time 702ms
Memory 30160kB
Length 2393
Lang C++
Submitted 2019-06-17 07:39:27
RemoteRunId 29447798

但是美中不足的地方在于Memory占用太高了——30MB之多, 可见，如果内存卡的比较死的话，可能就过不了，所以本题只能算水过.

本来写了一个

1
2
3
4
5
6
7
8
void freeTree(LeftHeap tree) // 释放树
{
	if (!tree) return;
	freeTree(tree->left);
	freeTree(tree->right);
	delete tree;
	tree = 0;
}

然后每个测试用例，调用一次

1
for (int i=1;i<=n; freeTree(b[i])); // 释放树，不然可能MLE

但是竟然报

1
Runtime Error(ACCESS_VIOLATION)

非法访问. 后来debug才知道原因.

上图左边和右边分别是运行过程中b[1]和b[2]. 可以看到, freeTree(b[1])的时候，已经将两个画圈的内存内容释放回操作系统了，但是右边再来释放的时候, 两个画圈的里面都是乱的. 本质原因是因为右边其实是野指针非法访问已经回收的内存. 所以oj才会报 ACCESS_VIOLATION. 以后再想解决办法吧~

参考

【1】https://yfsyfs.github.io/2019/06/12/%E5%B7%A6%E5%BC%8F%E5%A0%86/

【2】https://yfsyfs.github.io/2019/05/24/%E5%B9%B6%E6%9F%A5%E9%9B%86%E6%A8%A1%E6%9D%BF/