Vijos-P 1097-合併果実(単純欲張り&&優先キュー&&c++)

P 1097合併果実
Accepted
ラベル:欲張りNOIP向上グループ2004
説明
一つの果樹園では、多くの果物がすべて打たれ、果物の種類によって異なる山に分かれている.すべての果物をたくさん合成することにした.合併するたびに、多くの場合、2つの果物を統合することができ、消費された体力は2つの果物の重量の和に等しい.すべての果物はn-1回の合併を経て、1山しか残っていないことがわかる.果物を合併するときに消費される体力の多くは、合併するたびに消費される体力の和に等しい.これらの果物を家に運ぶのに力を入れなければならないので、果物を合併するときはできるだけ体力を節約しなければならないことが多い.各果物の重量が1であり、既知の果物の種類数と各果物の数を仮定すると、あなたの任務は合併の順序案を設計し、多くの体力を最小限に抑え、この最小の体力消費値を出力することです.例えば3種類の果物があり、数は1,2,9の順である.まず1、2スタックを統合することができ、新しいスタックの数は3で、体力を消費するのは3です.次に、新しいスタックを元の第3のスタックと統合し、新しいスタックを得、数は12であり、体力は12である.そのため、体力=3+12=15を多く消費します.15が最小の体力消費値であることが証明される.
書式設定
入力フォーマット
入力は2行を含み、1行目は整数n(1<=n<=10000)であり、果物の種類数を表す.2行目はn個の整数を含み、スペースで区切られ、i番目の整数ai(1<=ai<=20000)はi番目の果物の数である.
出力フォーマット
出力には1つの整数、すなわち最小の体力消費値しか含まれない行が含まれます.入力データは、この値が2^31未満であることを保証します.
サンプル1
サンプル入力1[コピー]

3 
1 2 9

サンプル出力1[コピー]

15 

制限
各試験点1 s
ソース
NOIp 2004
大牛が彼のすばらしいアルゴリズムを分かち合うことに感謝します!!

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
priority_queue<int>q;                 //c++STL      ，                    
int main()
{
    int n,i,x,a=0,t;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>x;
        q.push(-x);                  //                     
    }
    for(i=1;i<n;i++)
    {
        t=q.top();                  //t              ,             
        a-=q.top();                 //a         
        q.pop();
        t+=q.top();
        a-=q.top();
        q.pop();
        q.push(t);
    }
    cout<<a;
    return 0;
}