我是靠谱客的博主 顺心小白菜,这篇文章主要介绍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),每根木棍的长度为 Li (1 ≤ Li ≤ 50,000) 。现在他要把这N根木棍连接在一起,每次连接只能把两根木棍连在一起,而且每连接一次都需要花费一些money去买材料,买这些材料要用的money和要连接的两根木棍的长度之和相等(如:把长度分别为5和8的木棍连在一起,买材料就需要花13元)。Bingo想要花最少的钱来买材料。我们已经知道了他找到的木棍的长度,那么他最少要花多少钱来买材料呢??

Input

 
第一行为Bingo找到的木棍的数目N(N为整数),之后N行为每根木棍的长度。

Output

Bingo 所需要买材料的最少money

Sample Input






8

 











Sample Output

48

 









Hint

5
4
3
6
1
8
48
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过不了)

代码如下:

复制代码
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
#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; }



最后

以上就是顺心小白菜最近收集整理的关于POJ:3253 Fence Repair(优先队列)的全部内容,更多相关POJ:3253内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(88)

评论列表共有 0 条评论

立即
投稿
返回
顶部