Tyvj 1066合併果実(欲張り)

時間:1000 ms/空間:131072 KiB/Javaクラス名:Main
背景
NOIP 2004向上グループ第2パス
説明
一つの果樹園では、多くの果物がすべて打たれ、果物の種類によって異なる山に分かれている.すべての果物をたくさん合成することにした. 
合併するたびに、多くの場合、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
出力フォーマット
出力には1つの整数、すなわち最小の体力消費値しか含まれない行が含まれます.入力データは、この値が2^31未満であることを保証します. 
試験例1
入力
3 
1 2 9
しゅつりょく
15
コメント
30%のデータに対して、n<=1000が保証されています.
50%のデータに対して、n<=5000が保証されている. 
すべてのデータに対して、n<=10000が保証される. 
中国語の問題、題意は解釈しないで、最初はこの問題を見て、以前した貪欲な問題と少し似ていると思って、大体の構想はつまり、先に2つの最小のものを見つけて、取り出して、加えて更に入れて、しかし私は1つの致命的な間違いを犯して、私は毎回取る前に残りのものを並べ替えて、時間のタイムアウトを招いて、その後、並べ替えずに最小の和次小を見つけて、それらを加えて入れて、並べ替えの時間を節約して、直接過ぎました.試合が終わった後、他の人が優先キューでやっているのを聞いて、自分でもやってみましたが、実は簡単で、品質の小さい列から大きい列を定義して、毎回2つ出て、1つ(入隊したのは出て2つの数の和)に入って、このようにソートしなくてもいいので、同じように过ごすことができます.
ACコード:

#include
#include
using namespace std;
int a[10010],n;
void df(int x)
{
    int i,t,q;
    q=x;
    for(i=q+1;i<=n;i++)
    {
        if(a[i]

優先キュー:

#include
#include
#include
#include
using namespace std;
struct node
{
    int m;
    bool operatorQ;
    node p,q;
    while(~scanf("%d",&n))
    {
        for(i=0; i