お菓子の合併(欲張り+優先列)


C-結合果実
Crawling in process…
Crawling failed
Time Limit:1000 MS Memory Limit:13137172 KB 64 bit IO Format:%lld&%ll u
スーパースター
Description
今はn山の果物があります.i番目の山にai個の果物があります.今はこれらの果実を一つの山にまとめます.毎回の合併の価格は二つの果物の総果実数です.すべての果実の最小価格を統合することを求めます.
Input
最初の行は整数T(T<=50)を含み、データのグループ数を表します.各グループのデータの最初の行は、1つの整数n(2<==n==1000)を含み、果実の山の数を表しています.2行目はn個の正の整数ai(ai<=100)を含み、果物の山ごとの数を表します.
Output
各グループのデータは1行のみで、最小のマージ価格を表します.
Sample Input
 
     
2
4
1 2 3 4
5
3 5 2 1 4
Sample Output
 
     
19
33
ベント
優先列の応用は、実際にはハフマンアルゴリズムに相当しています.最小の二つの山を取って統合し、統合後の山を同じ大きさで比較します.優先キューについては、参照できます.http://blog.csdn.net/qq_3076791/articale/detail/50569241
#include
#include
#include
using namespace std;
int main()
{
    int t,n,a;
    scanf("%d",&t);
    while(t--)
    {
        priority_queue,greater >q;
        scanf("%d",&n);
        for(int i=0; i=2)
        {
            tmp=0;
            tmp+=q.top();
            q.pop();
            tmp+=q.top();
            q.pop();
            ans+=tmp;
            q.push(tmp);
        }
        printf("%d
",ans); } return 0; }
優先列を使って問題をするのは初めてです.二つの点に注意が必要です.
【1】priority_queue,greater >q;      >>        ;
【2】        q.top(),   q.front()。