Stamps problem - SPOJ

Problem solving with programming: Stamps problem - SPOJ

You need to collect some stamps from friends. Suppose you have n friends and each of them have some stamps with them {s₁, s₂, ... s_n}.
 

The problem is to find if we can collect the targeted number of stamps. If it is possible, we have to find the minimum number of friends to collect the stamps from.

We may use Heap, PriorityQueue.

 for( i = 0 ; i < t; i++ )


 {


  int need;


  cin >> need;


  int n;


  cin >> n; // number of friends


  vector<int> stamps(n);


  


  int j;


  for( j = 0; j < n; j++ )


  {


   cin >> stamps[j];


  }


  //find the sum of all stamps from friends; use library algorithm


  long long total = accumulate(stamps.begin(), stamps.end(), 0 );


  


  if( total < need )


  {


   cout << "Scenario #" << (i+1) << ":" << endl << "impossible" << endl << endl;


  }


  else


  {


   //sort coins in descending order; use library algorithm


   sort( stamps.begin(), stamps.end(), greater<int>() );


   long long t = 0;


   j = 0;


   //borrow until you jave just enough stamps


   while ( t < need )


   {


    t += stamps[j];


    j++;


   }


   //we need to borrow from j friends


   cout << "Scenario #" << (i+1) << ":" << endl << j << endl << endl;


  }

Read full article from Problem solving with programming: Stamps problem - SPOJ