SRM 486 div2 hard: CrazyLine
ぶっちゃけ Crazy ではない。
解法
明らかにデコボコに人を並べるのが良いです。
大まかな方針としては, 背の高さを低い方から半分, もう半分に分けて, 奇数番目に背の低い人, 偶数番目に背の高い人を並べるようにする, というのが良いです。
図にするとこんな感じです。□が背の高い人, ○が背の低い人です。
矢印は, 背の低い人が差を取る人を表していますが, 端っこの人は差を取る人が少ないので, 真ん中らへんの身長を端っこに寄せたほうが 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; } };