나무 - 쌓 기 구조 연습 - 과일 을 합 친 하프 만 트 리 Time Limit: 1000 MS Memory Limit: 65536 KB Submit Statistic Discuss Problem Description

나무 - 더미 구조 연습 - 과일 을 합 친 하프 만 나무
Time Limit: 1000MS 
Memory Limit: 65536KB
Submit  Statistic  Discuss
Problem Description
 한 과수원 에 서 는 이미 모든 열 매 를 따 냈 고, 과일의 종류 에 따라 다른 더미 로 나 누 었 다.모든 과일 을 한 무더기 로 합성 하기 로 많이 결정 하 세 요.
매번 합병 할 때마다 두 무더기 의 과일 을 한데 모 을 수 있 고 소모 하 는 체력 은 두 무더기 의 과일 무게 의 합 과 같다.모든 과일 이 n - 1 차 합병 을 거 친 후에 한 무더기 만 남 았 음 을 알 수 있다.과일 을 합병 할 때 총 소모 되 는 체력 은 합병 할 때마다 소모 되 는 체력 과 같다.
이 과일 들 을 집 으로 옮 기 는 데 많은 힘 을 들 여야 하기 때문에 과일 을 합 칠 때 가능 한 한 체력 을 절약해 야 한다.모든 과일의 무 게 를 1 로 가정 하고 과일의 종류 수 와 모든 과일의 수 를 알 고 있 습 니 다. 당신 의 임 무 는 합병 순서 방안 을 설계 하여 많은 체력 을 최소 화하 고 이 최소 의 체력 소모 치 를 수출 하 는 것 입 니 다.
예 를 들 어 세 가지 과일 이 있 는데 그 수 는 1, 2, 9 이다.먼저 1, 2 더 미 를 합 칠 수 있 고, 새 더 미 는 3 이 며, 체력 소 모 는 3 이다.이 어 새 더 미 를 기 존의 세 번 째 더 미 를 합 쳐 새로운 더 미 를 얻 었 고, 숫자 는 12 이 며, 체력 은 12 이다.그래서 체력 을 많이 소모 한다 = 3 + 12 = 15.15 가 최소 체력 소모 치 임 을 증명 할 수 있다.
 
Input
 첫 번 째 줄 은 하나의 정수 n (1 < = n < = 10000) 으로 과일의 종류 수 를 나타 낸다.두 번 째 줄 은 n 개의 정 수 를 포함 하고 빈 칸 으로 구분 하 며, i 번 째 ai (1 < = ai < = 20000) 는 i 번 째 열매 의 수량 입 니 다.
 
Output
 출력 은 한 줄 을 포함 합 니 다. 이 줄 은 하나의 정수 만 포함 합 니 다. 즉, 가장 작은 체력 소모 값 입 니 다.입력 데 이 터 는 이 값 이 2 ^ 31 보다 작 음 을 보증 합 니 다.
 
Example Input

3
1 2 9

Example Output

15

 
   
 
   
         。。。             = =
  
 
   
#include 
using namespace std;
int main()
{
    int i,j;
    int n;
    priority_queue,greater >q;
    while(cin>>n)
    {
        while(n--)
        {
            int x;
            cin>>x;
            q.push(x);
        }
        int sum=0;
        while(q.size()!=1)
        {
            int t1=q.top();
            sum+=t1;
            q.pop();
            int t2=q.top();
            q.pop();
            sum+=t2;
            int x=t1+t2;
            q.push(x);
        }
        printf("%d
",sum);
    }
    return 0;
}