[优先队列]的应用 priority_queque p164王道 哈弗曼树

//[优先队列]的应用 priority_queque p164王道
#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
using namespace std;
struct Complex{
    int real;
    int imag;
    Complex(int a,int b):real(a),imag(b){}
    bool operator< (Complex c) const{
        if(real*real + imag*imag == c.real*c.real+c.imag*c.imag)
            return imag>c.imag;
        else
            return real*real + imag*imag < c.real*c.real+c.imag*c.imag;
    }
};
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        priority_queue<Complex> myPriorityQueue;
        while(n--){
            string str;
            cin >> str;
            if (str == "Pop") {
                if(myPriorityQueue.empty()) printf("empty\n");
                else{
                    Complex current = myPriorityQueue.top();//不是front()
                    myPriorityQueue.pop();
                    printf("%d+i%d\n",current.real,current.imag);
                    printf("SIZE = %d\n",myPriorityQueue.size());

                }
            }else{
                int a,b;
                scanf("%d+i%d",&a,&b);
                myPriorityQueue.push(Complex(a,b));
                printf("SIZE = %d\n",myPriorityQueue.size());
            }
        }
    }
    return 0;
}
/**

 边界值检测  牛客网上OJ漏掉了
3
Insert 3+i4
SIZE = 1
Insert 4+i3
SIZE = 2
Pop
4+i3
SIZE = 1


 */

//优先队列 哈弗曼树 P169
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        priority_queue<int,vector<int>,greater<int> > myPriorityQueue;
        int x;
        while(n--){
            scanf("%d",&x);
            myPriorityQueue.push(x);
        }
        int answer = 0;
        while(myPriorityQueue.size() > 1){
            int a = myPriorityQueue.top();
            myPriorityQueue.pop();
            int b = myPriorityQueue.top();;
             myPriorityQueue.pop();
            answer += a+b;
            myPriorityQueue.push(a+b);
        }
        
        printf("%d\n",answer);
    }
    
    return 0;
}