题解 | #搬水果#

#include <stdio.h>
#include <stdlib.h>
/*根据下面注释的失败思路进行改进
上面思路失败的点在于把每次合并后的最小堆考虑成了各个种类里面的最小堆
只需要想办法维护一个每次都能输出最小两个堆的存储结构即可
对于C++来说可以采用优先队列
对于C来说,其实就是建树的过程,思路类似于哈夫曼树,最终题目要求的就是WPL
简化一下用数组排序+递归的思想去求
*/
int cmp(const void* a,const void* b)
{
    int c = *(int*) a;
    int d = *(int*) b;
    return c-d; //升序排列
}

int getHuffmanWpl(int arr[],int start,int len)
{
    int sum,temp,i;
    if(len == start)
    {
        return 0; //递归边界
    }
    if(len == start + 1)
    {
        return arr[0]; //只有一个元素的时候
    }
    if(len == start + 2)
    {
        return arr[start] + arr[start+1];
    }
    sum = arr[start] + arr[start+1];
    arr[start+1] = sum; //找个地方存储sum,之后从sum这里截断数组
    for(i=start+1;i<len-1;i++)
    {
        //冒泡
        if(arr[i+1] < sum)
        {
            arr[i] = arr[i+1];
        }
        else
        {
            break;
        }
    }
    arr[i] = sum;
    return sum+getHuffmanWpl(arr, start+1, len);//递归截断数组
}

int getWpl(int arr[],int n)
{
    qsort(arr,n, sizeof(int), cmp);
    //或者用冒泡
    return getHuffmanWpl(arr, 0, n);
}


int main()
{
    int count;
    while (scanf("%d",&count) != EOF)
    {
        if(count == 0)
        {
            break;
        }
        int fruits[count];
        int i,Wpl;
        for(i=0;i<count;i++)
        {
            scanf("%d",&fruits[i]);
        }
        Wpl = getWpl(fruits, count);
        printf("%d\n",Wpl);
    }    
}