TeamSplit
SRM 242 · 2005-05-14 · by gepa
Problem Statement
You want to split some people into two teams to play a game.
In order to make the split, you first designate two
team captains who take alternate turns selecting players for their teams.
During each turn, the captain selects a single player for his team.
Since each captain wants to make the strongest possible team, he will
always select the best available player.
The players have strengths, which are given in the
For example, if strengths={5,7,8,4,2}, then the first captain selects the player with strength 8 for his team, the second captain gets the player with strength 7, the first gets the one with strength 5, the second the one with strength 4, and the last one (strength 2) goes to the first team. The first team now has a total strength 8+5+2=15, and the second team has strength 7+4=11.
Return the absolute strength difference between the two teams. For the example above you should return 4 (=15-11).
Constraints
- strengths will have between 1 and 50 elements, inclusive.
- Each element of strengths will be between 1 and 1000, inclusive.
{5,7,8,4,2}
Returns: 4
The example from the problem statement.
{100}
Returns: 100
A boring game with only one player. The second team has strength 0 (no players).
{1000,1000}
Returns: 0
Both teams with equal strength.
{9,8,7,6}
Returns: 2
{1,5,10,1,5,10}
Returns: 0
Submissions are judged against all 66 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TeamSplit with a public method int difference(vector<int> strengths) · 66 test cases · 2 s / 256 MB per case