题意：

输入一串数据，拿出两个相加，把和放回去，再拿出两个相加，把和放回去……依次循环，最后找出最小的和。

思路：

使用优先队列+贪心，队列按从小到大排列，每次选出队首最小的2个数据，计算之后把和再放回队列。也就是哈夫曼编码算法。

Using a Priority Queue, you can greedily take the two smallest numbers, add them and insert them back into the Priority Queue. 1 #include <iostream>

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;class T{    public :        int n;};bool operator < (const T &t1, const T &t2){     return t1.n > t2.n;}class AddAll{    private:        priority_queue
          
            pri_que; int sum; public: void init(); void process();// void output();};void AddAll::init(){ while(!pri_que.empty())pri_que.pop(); sum = 0;}void AddAll::process(){ int num; T temp; while(cin>>num){ if (num == 0)break; init(); while(num--){ cin>>temp.n; pri_que.push(temp); } while(!pri_que.empty()){ T top1 ,top2 ,sumTop; top1 = pri_que.top(); pri_que.pop(); if(!pri_que.empty()){ top2 = pri_que.top(); pri_que.pop(); } else top2.n = 0; sumTop.n = top1.n + top2.n; sum = sumTop.n + sum; if(!pri_que.empty()) pri_que.push(sumTop); } cout<
           
            <
           
          
         
        
       
      
     

 

注意：要重载'<'，使优先队列从小到大排列。

 

测试数据：

数据来源：http://www.algorithmist.com/index.php?title=UVa_10954

 

Input

31 2 341 2 3 410100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 52 2 2 2 30

 

 

 

 

 

 

 

Output 

919340000026