791. 合并数字

作者: 和蔼的zhxing | 来源:发表于2018-02-05 19:54 被阅读35次

    给出n个数,现在要将这n个数合并成一个数,每次只能选择两个数a,b合并,每次合并需要消耗a+b的能量,输出将这n个数合并成一个数后消耗的最小能量。

    注意事项

    2 <= n <= 50000,合并后的数字不会超过int范围

    样例
    给出[1,2,3,4],返回 19

    解释:
    选择1,2合并,消耗3能量,现在为[3,4,3],选择3,3合并,消耗6,现在为[6,4],剩下两个数合并,消耗10,一共消耗19。
    

    给出[2,8,4,1],返回 25

    解释:
    选择1,2合并,消耗3能量,现在为[8,4,3],选择3,4合并,消耗7,现在为[7,8],剩下两个数合并,消耗15,一共消耗25。
    

    贪心算法

    一个显而易见的策略是每次我们都找到最小的两个来合并,这样最后加起来的能量应该是最小的。这样想倒是很简单,我们可以对vector<int>进行排序,取出前两个(从vector中删掉)进行相加,然后把结果重新放入vector<int>中。然后再排序,重新进行上述步骤,直到vector中只剩下一个数据,就是我们要找的。但是这样显然是非常耗时的,且不说vector排序耗时,删除也是很耗时的。
    一种比较好的数据结构是优先队列,这个是用堆实现的,queue这个数据结构。

    priority_queue 优先队列
    priority_queue<Type, Container, Functional>
    Type为数据类型, Container为保存数据的容器,Functional为元素比较方式。后两种可以不写,如果不写,container默认为vector,functional默认为大的在队首。
    成员函数主要有:

    函数 功能
    empty(); //判断是否为空
    size(); //返回大小
    pop(); //删除队首
    push(); //入队
    top(); //返回队首

    默认大元素优先,因为我们要用小元素优先,所以应该构造,:
    priority_queue<int,vector<int>,greater<>> q
    functional参数是一个bool型的比较参数,和STL中sort里的那个参数是一样的。可以自定义。
    了解了这个,剩下的程序就比较简单了:

        int mergeNumber(vector<int> &numbers) {
            int res=0;
            if(numbers.size()==1)
            return *numbers.begin();
            
            priority_queue<int,vector<int>,greater<>>  q;   //优先队列,小的在前
            for(auto n:numbers)      //所有数据入队
            {
                q.push(n);
            }
            int sz=numbers.size();
            int q1=0;
            int q2=0;
            while(sz!=1)
            {
                q1=q.top();       //取第一个元素
                q.pop();
                q2=q.top();       //取第二个元素
                q.pop();
                res+=q1+q2;       //和累加起来
                q.push(q1+q2);    //和入队
                sz--;             //sz--
            }
    
            return res;
        }
    

    相关文章

      网友评论

        本文标题:791. 合并数字

        本文链接:https://www.haomeiwen.com/subject/kzjizxtx.html