This problem is from SPOJ. Give it a try by following this link!
The simplified problem statement is as follows.
You need to collect some stamps from friends. Suppose you have n friends and each of them have some stamps with them {s1, s2, … sn}.
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.
For example. Let us assume we have a target of 100 stamps, and we have 5 friends with {27, 68, 39, 4, 51} stamps.
We just need to collect from 2 friends to achieve the target {68,51}.
The solution is simple.
- First check the sum of stamps from all the friends is sufficient to reach the target.
- If it is possible just sort the friends in descending order of the number of stamps they have.
- Keep collecting the stamps from them until have just enough stamps to reach the target.
Here is the C++ implementation of the above algorithm.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| #include <algorithm> // for sort() | |
| #include <numeric> //for accumulate() | |
| using namespace std; | |
| int main() | |
| { | |
| int t; | |
| cin >> t; | |
| int i; | |
| 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; | |
| } | |
| } | |
| return 0; | |
| } |
by