首页 > POJ解题报告 > POJ 3253 Fence Repair[哈夫曼树]

POJ 3253 Fence Repair[哈夫曼树]

这个题就是一个哈弗曼树的问题,感觉对树的操作还是不太熟悉,这里再次借用STL里面的优先队列priority_queue来解决问题了。
不过,在Visual Studio的Debug模式下运行时竟然遇到一个问题,提示一个错误“stack around the variable n was corrupted”,感觉有点奇怪,网上虽然有那种很临时的解决方案:“把 Project->配置属性->C/C++ ->代码生成->基本运行时检查为 默认值”就不会报出异常,不过个人感觉这种解决方案毫无意义,因为你还是不知道问题出在哪里。而网上很多出错原因都是由于数组越界的问题,看来我这个有点特殊了。

看了下反汇编代码,没太明白哪里错误,只知道在main函数外边的一个Check失败了

00411BCB  call        @ILT+430(@_RTC_CheckStackVars@8) (4111B3h)

不过,提交还是可以AC的。

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
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
 
//#define __int64 long long
 
class Node
{
public:
	__int64 w;
	Node(__int64 weight = 0) : w(weight) {}
	bool operator<(const Node& rhs) const
	{
		return this->w > rhs.w;
	}
};
 
int main(int argc, char **argv)
{
	int n, i;
	while (EOF != scanf("%I64d", &n))
	{
		priority_queue<Node> q;
		__int64 tmp, res = 0;
		for (i = 0; i < n; ++i)
		{
			scanf("%I64d", &tmp);
			q.push(tmp);
		}
		Node na, nb;
		while (q.size() > 1)
		{
			na = q.top();
			q.pop();
			nb = q.top();
			q.pop();
			na.w += nb.w;
			res += na.w;
			q.push(na);
		}
		q.pop();
		printf ("%I64d\n", res);
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 3253 Fence Repair[哈夫曼树]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 本文目前尚无任何评论.