HeightRound
SRM 346 · 2007-04-24 · by soul-net
Problem Statement
There are several people that will sit around the same table in a circular fashion. Since all these people are very self-conscious about their height, you don't want to sit any short person next to a tall one. To formalize this, we want to minimize the maximum height difference between 2 adjacent persons.
You will be given the heights of the people as a
Constraints
- heights will contain between 3 and 50 elements, inclusive.
- Each element of heights will be between 1 and 1000, inclusive.
{1,2,3,4}
Returns: {1, 2, 4, 3 }
It's better to separate the tallest and shortest people in the round. All solutions with 1 and 4 separated are equivalent, so we choose the lexicographically first one.
{1000,500,1}
Returns: {1, 500, 1000 }
In a round of only 3 persons, everybody is next to everyone else, so we only have to return the lexicographically first representation.
{1,3,4,5,7}
Returns: {1, 3, 5, 7, 4 }
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
{1000,456,65,24,62,523,45,234,653,453,523,51,5,134,13,453,45,354,134,312,523,923,452,345,845,234,523,523,45,235,234,523,452,345,9,75,4,345,31,123,54,5,54,54,543,25,45,4,999,1000}
Returns: {4, 4, 5, 5, 9, 13, 24, 25, 31, 45, 45, 45, 45, 51, 54, 54, 54, 62, 65, 75, 123, 134, 134, 234, 234, 234, 312, 345, 345, 345, 354, 452, 452, 453, 453, 456, 523, 523, 523, 523, 523, 543, 845, 999, 1000, 1000, 923, 653, 523, 235 }
Submissions are judged against all 173 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HeightRound with a public method vector<int> getBestRound(vector<int> heights) · 173 test cases · 2 s / 256 MB per case