Time Limit: 1 second
Memory Limit: 50 MB
【问题描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。【输入】
共2行；
第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。
第二行是第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。
【输出】
包含1行,这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
【输入样例】
3 1 2 9
【输出样例】
15
【 数据规模】
30%的数据满足：n<=100050%的数据满足：n<=5000
100%的数据满足：n<=10000
【题解】
法一:将所有的果子数目快排一遍，然后合并前两个。再把合并的放到序列中(插入排序)
重复此步骤n-1次即可。
法二:用一个小根堆来维护整个序列的最小值。建堆的话，一开始要从倒数第二层开始建。然后往下调整。这样可以保证建堆是正确的。然后依然是重复n-1次操作。每次操作：先取出dui[1]即堆中的最小值。然后把堆尾的元素放到1位置。然后堆的大小递减。然后从1开始往下进行调整。维护堆。取出来的第一个数字为a，然后同样的，取出经过维护之后的堆中的第一个元素即最小值，设为b，然后堆的大小递减。同样从第一个元素开始往下调整堆。然后c=a+b，再把堆的大小递增，把c放到堆的最后面。然后从堆的最后一个位置往上进行调整。获取这个新插入的元素它最后的位置。然后从那个位置再往下进行调整即可。然后重复此步骤n-1次即可。
【代码】
#include <cstdio>
int n,dui[20001],size,pos,sum = 0;
void down_tiaozheng(int p) //往下调整
{
int x =dui[p]; //先记录要被调整的数字的大小。
int i = p,j = p*2; //p*2就表示其左儿子
while (j <= size) //如果没有超过树的范围
{
if (j < size && dui[j+1] < dui[j]) //获取它们之中较小的那个数。这样经过调整这个dui[j]
j++; //可能会往上交换。也能满足每个节点都比儿子节点小了。
if (x > dui[j]) //如果要进行交换 则交换
{
dui[i] = dui[j];
i = j;
j = i*2;
} //不用交换就可以结束了。
else
break;
}
dui[i] = x; //把x放到某个位置;
}
void up_tiaozheng(int p) //往上调整
{
int x = dui[p]; //记录下要调整的数字大小
int i = p,j = p/2; //除2表示往上进行调整 即其父亲节点。
while (j > 0) //如果没有超过树的范围。则继续
{
if (dui[j] > x) //父节点只有一个。所以不用再判断了。
{
dui[i] = dui[j];//进行调整
i = j;
j = j/2;
}
else //如果不会出现冲突了
break; //就结束调整的过程。
}
dui[i] = x; //把它调整到i位置
pos = i; //然后记录它调整到了哪个位置。方便之后再往下调整。
}
void input_data()
{
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%d",&dui[i]);
size = n;
}
void get_ans()
{
for (int i = (n/2);i>=1;i--) //输入数据完之后要进行建堆的操作，从倒数第二层开始调整以建堆
down_tiaozheng(i);
for (int i = 1;i <= n-1;i++)
{
int a = dui[1]; //取出两次堆中的第一个元素。然后调整两次堆。(取完就调整)
dui[1] = dui[size];
size--;
down_tiaozheng(1);
int b = dui[1];
dui[1] = dui[size];
size--;
down_tiaozheng(1);
int c = a+b;
sum+=c;
size++;
dui[size] = c; //把累加的c加到堆中
up_tiaozheng(size); //先往上调整。再往下调整。
down_tiaozheng(pos);
}
}
void output_ans()
{
printf("%d
",sum);
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
input_data();
get_ans();
output_ans();
return 0;
}