p 1090【noip 2004改良组】联合果/【usaco 06 nov】栅栏修复G
题目描述
在一个果园里，多多把所有的水果都击倒了，并根据不同的水果种类把它们分成不同的堆。多多决定把所有的水果组合成一堆。
每次合并，多多可以将两堆水果合并在一起，消耗的体力等于两堆水果的重量之和。可以看出所有的水果都经过n-1n？一次合并后，只剩下一堆了。合并果实消耗的总体力等于每次合并消耗的体力之和。
因为要花大力气把这些水果搬回家，所以在合并水果的时候要尽量节约能源。假设每个水果的重量为11，水果的种类数和每种水果的数量都是已知的，那么你的任务就是设计一个组合序列方案，使更多的水果消耗的体力最小，并输出这个最小体力消耗值。
比如水果有33种，依次是11种、22种、99种。首先，11堆和22堆可以合并。新桩数33根，能耗33。然后将新桩与原第三桩合并，得到新桩，编号为1212，体力为1212。所以需要很大的体力=3 12=15=3 12=15。可以证明1515是最小物理消耗值。
输入格式
总共两排。
第一行是整数n(1n10000)，表示水果的种类数。
第二行包含由空格分隔的n个整数，第I个整数ai？(1ai？20000)是第I个水果的数量。
输出格式
整数，即最小体力消耗值。输入数据以确保该值小于2 {31}。
输入输出样例
输入#1副本。
三
1 2 9
输出#1副本
15
说明/提示
对于30%的数据，确保n1000:
对于50%的数据，确保n5000；
对于所有数据，确保n10000。
分析
从观察可以看出，合并得越早，计算的次数越多，所以贪心策略是先合并小堆。
#includebits/stdc。h
使用命名空间标准；
int n；
priority_queueint，vectorint，greater int a；
int ans
int main()
{
cinn
for(int I=1；I=n；(一)
{
int p；
cinp
a . push(p)；
}
而(a . size)(1)
{
int j=a . top()；
a . pop()；
int k=a . top()；
a . pop()；
ans=(j k)；
a . push(j . k)；
}
coutansendl
返回0；
}
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/100410.html