SRM486 Div2 Hard(1000) CrazyLine

CrazyLine

中央値xより低い生徒と高い生徒を交互に並べるとそれぞれの生徒のcrazinessへの寄与は2abs(heights[i]-x)。ただし両端の生徒はこれより小さいので、中央値付近の生徒を両端に置く。生徒数が奇数の場合は選び方が２通りあるので、よりcrazinessの大きい方を答えにする。

#include <vector>
#include <algorithm>
using namespace std;

class CrazyLine{public:
int maxCrazyness( vector <int> heights )
{
    int n = (int)heights.size();

    if ( n == 1 )
        return 0;

    sort( heights.begin(), heights.end() );
    
    int ans = 0;

    if ( n % 2 == 0 )
    {
        for ( int i=0; i<n/2-1; i++ )
            ans += ( heights[n/2-1] - heights[i] ) * 2;
        ans += heights[n/2] - heights[n/2-1];
        for ( int i=n/2+1; i<n; i++ )
            ans += ( heights[i] - heights[n/2-1] ) * 2;
    }
    else
    {
        int ans1 = 0;
        for ( int i=0; i<n/2; i++ )
            ans1 += ( heights[n/2] - heights[i] ) * 2;
        ans1 += heights[n/2+1] - heights[n/2];
        for ( int i=n/2+2; i<n; i++ )
            ans1 += ( heights[i] - heights[n/2] ) * 2;

        int ans2 = 0;
        for ( int i=0; i<n/2-1; i++ )
            ans2 += ( heights[n/2] - heights[i] ) * 2;
        ans2 += heights[n/2] - heights[n/2-1];
        for ( int i=n/2+1; i<n; i++ )
            ans2 += ( heights[i] - heights[n/2] ) * 2;

        ans = max( ans1, ans2 );
    }

    return ans;
}};