POJ 3253

我们的小伙伴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
5
3
4
6
1
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；

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define M 22000
struct node
{
LL p;
friend bool operator <(node t1, node t2)
{
return t1.p > t2.p;//木棍的排序 先连最小的两个 
}
};
node a[M], ans;
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
priority_queue<node> q;
int i;
for(i=0; i<n; i++)
{
scanf("%d", &a[i].p);
q.push(a[i]);
}
if(n == 1)
{
printf("%lldn", a[0]);
continue;
}
LL a1, a2, sum = 0;
while(!q.empty())
{
a1 = q.top().p;
q.pop();
if(!q.empty())
{
a2 = q.top().p;
q.pop();
ans.p = a1 + a2;
q.push(ans);
}
else
{
ans.p = 0;
}
sum += ans.p;
}
printf("%lldn", sum);
}
return 0;
}

最后

以上就是细腻美女为你收集整理的POJ 3253的全部内容，希望文章能够帮你解决POJ 3253所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。