CrazyLine
SRM 486 · 2010-03-12 · by soul-net
Problem Statement
A rigorous teacher makes all his students stand in a line before entering the classroom. Being a rigorous teacher, he makes the students line up in non-descending order by height. One time, while the students were lining up, the teacher had to go to the bathroom. The students took the opportunity to play with the teacher's head and make a crazy line. They defined the craziness of a line as the sum of the absolute difference in height between each pair of consecutive students. Since a line ordered by height has minimum craziness, they of course decided to arrange themselves in a line with maximum craziness.
You are given a
Constraints
- heights will contain between 1 and 50 elements, inclusive.
- Each element of heights will be between 1 and 1000, inclusive.
{5,10,25,40,25}
Returns: 100
If the line is arranged in this order: 25-10-40-5-25, the sum of the differences is 15+30+35+20=100.
{2,3,5,7,11,13,17,19}
Returns: 82
The following order is optimal: 7-17-5-13-2-19-3-11.
{1,1,1,1,1,1,501}
Returns: 1000
Make sure to place the tall guy in the middle.
{1000,1000,1000,1000,1000,1000,1000,1000,1000}
Returns: 0
There is not much difference.
{1,1,1,1,1,1,1,500,500,500,500,1000,1000,1000,1000}
Returns: 10986
Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CrazyLine with a public method int maxCrazyness(vector<int> heights) · 110 test cases · 2 s / 256 MB per case