POJ：3253 Fence Repair（优先队列）

87 阅读 0 评论 58 点赞

我是靠谱客的博主顺心小白菜，这篇文章主要介绍POJ：3253 Fence Repair（优先队列），现在分享给大家，希望可以做个参考。

F - VI

Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu

Submit Status

Description

我们的小伙伴Bingo真的很调皮，他在上课的路上看到树上有个鸟窝，他就想去把他捅下来，但是鸟窝很高他够不到，于是他就到处找木棍，想把这些木棍接在一起，然后去捅鸟窝。他一共找了N跟木棍 (1 ≤ N ≤ 20,000)，每根木棍的长度为 L_i (1 ≤ L_i ≤ 50,000) 。现在他要把这N根木棍连接在一起，每次连接只能把两根木棍连在一起，而且每连接一次都需要花费一些money去买材料，买这些材料要用的money和要连接的两根木棍的长度之和相等（如：把长度分别为5和8的木棍连在一起，买材料就需要花13元）。Bingo想要花最少的钱来买材料。我们已经知道了他找到的木棍的长度，那么他最少要花多少钱来买材料呢？？

Input

第一行为Bingo找到的木棍的数目N（N为整数），之后N行为每根木棍的长度。

Output

Bingo 所需要买材料的最少money

Sample Input

5
3
4
6
1
8

Sample Output

Hint

Bingo第一次要把长度为1和3的木棍接在一起，需要的monye为4；

第二次要把长度为4和4的木棍接在一起，需要的money为8；

第三次要把长度为6和8的木棍接在一起，需要的money为14；

第四次要把长度为8和14的木棍接在一起，需要的money为22；

所以总共需要4+8+14+22=48；

这道题找不到出处，但是和POJ上的一道题一样（http://poj.org/problem?id=3253）

解题思路：优先队列，优先用小的连接，注意求的是总的用钱数。（注意数据用__int64型的，int过不了）

代码如下：

#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
struct node
{
	__int64 a;
	friend bool operator<(node x,node y)
	{
		return x.a>y.a;
	}
};
int main()
{
	__int64 n;
	struct node tmp;
	priority_queue<node>q;
	scanf("%I64d",&n);
	if(n==1)//当是一个的时候，就这么办，两个以上的适合下面的程序 
	{
		__int64 a;
		scanf("%I64d",&a);
		printf("%I64dn",a);
		return 0;
	}
	for(__int64 i=0;i<n;i++)
	{
		scanf("%I64d",&tmp.a);
		q.push(tmp);
	}
	struct node ans;//中间临时变量 
	__int64 answer=0;//money总 
	while(q.size()>1)//最后肯定里面剩一个 
	{
		ans.a=q.top().a;
		q.pop();
		ans.a=ans.a+q.top().a;
		q.pop();
		q.push(ans);
		answer=answer+ans.a;
	}
	printf("%I64dn",answer);
	return 0;
}