Click to jump to the problem

Decision

在一个果园里,小明已经将所有的水果打了下来,并按水果的不同种类分成了若干堆,小明决定把所有的水果合成一堆。每一次合并,小明可以把两堆水果合并到一起,消耗的体力等于两堆水果的重量之和。当然经过 n‐1 次合并之后,就变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。
假定每个水果重量都为 1,并且已知水果的种类数和每种水果的数目,你的任务是设计出合并的次序方案,使小明耗费的体力最少,并输出这个最小的体力耗费值。例如有 3 种水果,数目依次为 1,2,9。可以先将 1,2 堆合并,新堆数目为3,耗费体力为 3。然后将新堆与原先的第三堆合并得到新的堆,耗费体力为 12。所以小明总共耗费体力=3+12=15,可以证明 15 为最小的体力耗费值。

Input

每组数据输入包括两行,第一行是一个整数 n(1<=n<=10000),表示水果的种类数,如果 n 等于 0 表示输入结束,且不用处理。第二行包含 n 个整数,用空格分隔,第 i 个整数(1<=ai<=1000)是第 i 种水果的数目。

Output

对于每组输入,输出一个整数并换行,这个值也就是最小的体力耗费值。输入数据保证这个值小于 2^31。

Samples

Input

3
42 708 119 
4
749 522 629 823 
6
55 323 489 378 618 194 
0

Output

1030
5446
4935

Solution

哈夫曼编码问题
每次从数组中挑选出最小的两个数,将这两个数加入到体力消耗值,并将这两个数相加的结果放入数组,至到取完所有的元素
本题的关键在于如何取数组中最小的两个数:

  • 首先可以排除qsort()sort(),因为这两个算法的时间复杂度均为$O(nlogn)$,然后还需要遍历数组,总的时间复杂度在$O(n^2logn)$,稳稳地超时
  • 因为每次只需要取出最小的两个数,所以可以考虑使用小顶堆:建堆的时间复杂度为$O(n)$,每次调整堆的时间复杂度为$O(logn)$,总的时间复杂度为$O(n+logn)$
    使用C++的话,使用优先队列即可实现小顶堆的功能

使用C的话,我们需要手动建堆

Code

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxm (int)1e3
#define maxn (int)1e6
#define ms(a,b) memset(a,b,sizeof(a))
int a[maxn];
int n;
int INF=(1<<31)-1;
// 更改一个子树,使其变为小顶堆
void up_lheap(int l,int r)
{
    int father=l;
    int lson=l*2;
    int tmp=a[father];
    while(lson<=r)
    {
        if(a[lson]>a[lson+1]&&lson<r)
            lson++;
        if(tmp>a[lson])
        {
            a[father]=a[lson];
            father=lson;
            lson*=2;
        }
        else
            break;
    }
    a[father]=tmp;
}
// 得到一个完整的小顶堆
void create_heap()
{
    for(int i=n/2;i>=1;i--)
        up_lheap(i,n);
}
int main(int argc, char const *argv[])
{
    while(~scanf("%d",&n))
    {
        if(!n)
            break;
        ms(a,0);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int sum=0;
        int tmp=0;
        // 每次取出最小的两个元素,一共取n-1次
        for(int i=1;i<n;i++)
        {
            create_heap();
            sum+=a[1];
            tmp=a[1];
            a[1]=INF;
            create_heap();
            sum+=a[1];
            a[1]=tmp+a[1];
        }
        printf("%d\n",sum);
    }
    return 0;
}
/**************************************************************
    Problem: 1904
    User: wzy1999
    Language: C
    Result: 正确
    Time:602 ms
    Memory:4984 kb
****************************************************************/
Last modification:September 25th, 2020 at 07:39 pm
如果觉得我的文章对你有用,请随意赞赏