SRM 486 div2 hard: CrazyLine

ぶっちゃけ Crazy ではない。

問題

TopCoder Statistics - Problem Statement

解法

明らかにデコボコに人を並べるのが良いです。
大まかな方針としては, 背の高さを低い方から半分, もう半分に分けて, 奇数番目に背の低い人, 偶数番目に背の高い人を並べるようにする, というのが良いです。

図にするとこんな感じです。□が背の高い人, ○が背の低い人です。

矢印は, 背の低い人が差を取る人を表していますが, 端っこの人は差を取る人が少ないので, 真ん中らへんの身長を端っこに寄せたほうが craziness は大きくなります。

int calc(vi v) {
    int ans = 0;
    int n = v.size();
    for (int i = 0; i < n-1; i++) ans += abs(v[i]-v[i+1]);
    return ans;
}

class CrazyLine {
public:
    int maxCrazyness(vector <int> hs) {
        sort(hs.begin(), hs.end());
        int N = hs.size();
        if (N == 1) return 0;
        int n = N/2;
        vector<int> small, large;
        for (int i = 0; i < n; i++) small.push_back(hs[i]);
        for (int i = n; i < N; i++) large.push_back(hs[i]);
        reverse(small.begin(), small.end());
        int ret = 0;
        if (N%2 == 0) {
            for (int i = 0; i < N-n; i++) {
                if (i==0) ret += large[i];
                else ret += 2*large[i];
            }
            for (int i = 0; i < n; i++) {
                if (i == 0) ret -= small[i];
                else ret -= 2*small[i];
            }
        } else {
            for (int i = 0; i < N-n; i++) {
                if (i<=1) ret += large[i];
                else ret += 2*large[i];
            }
            for (int i = 0; i < n; i++) {
                ret -= 2*small[i];
            }
            small.clear(); large.clear();
            for (int i = 0; i <= n; i++) small.push_back(hs[i]);
            for (int i = n+1; i < N; i++) large.push_back(hs[i]);
            reverse(small.begin(), small.end());
            int tmp = 0;
            for (int i = 0; i < N-n-1; i++) {
                tmp += 2*large[i];
            }
            for (int i = 0; i <= n; i++) {
                if (i <= 1) tmp -= small[i];
                else tmp -= 2*small[i];
            }
            ret = max(ret, tmp);
        }
        return ret;
    }
};