Wednesday, March 7, 2012

My solution of UVA 10954 - Add All (using priority_queue)


10954 - Add All
* Similarity to Huffman coding problem.
* Solve by priority queue.


* Compare with 'min multiplication operation'the order of the variables/martix can not be rearranged/sort.


* Add All is easier and don't need dp[][].


* On the other hand, dp can be used if the order of the variables always fixed.


* Please notice how to define <priority_queue>:

        priority_queue<long long, vector<long long>, greater<long long> > l;


----- CODE -----
#include <iostream>
#include <algorithm>
#include <queue>


#define forr(i,b) for(int i=0;i<b;i++)
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define nl(c) c<<endl;
#define db(cout,c) tr(c,it){cout<<*it<<",";};nl(cout);


using namespace std;


int main(int argc, char *argv[])
{
    int N,a;
    while(cin>>N)
    {
        if(N==0)break;
        priority_queue<long long, vector<long long>, greater<long long> > l;
        forr(i,N){cin>>a;l.push(a);}
        long long sum=0LL;
        do{
            a=l.top();l.pop();
            a+=l.top();l.pop();
            sum+=a;
            l.push(a);
        }while(l.size()>1);
        cout<<sum<<endl;
    }
    return 0;
}

2 comments:

  1. i can't understand the priority_queue declaration!! what is the reason of vector and greater??

    ReplyDelete
    Replies
    1. It defines the type of element and the order of the queue.

      Delete