SRM 662 div1 easy:FoxesOfTheRoundTable
久しぶりに記事書きます。といっても書くことがない…
解法
@mayoko_ n+2とn+3を交換するとn+3とn+4が隣接してc+dは消滅しますが、今度はn+2とn+5の間にc+d+eが出来てしまいます。これはc+d以上なので小さくなっていません。こんな感じで、結局2つおきに並べるのが最適っぽいと思います。
— 宇宙ツイッタラーX (@kenkoooo) July 10, 2015
class FoxesOfTheRoundTable { public: vector <int> minimalDifference(vector <int> h) { int n = h.size(); vector<int> ret; vector<pii> P; P.resize(n); for (int i = 0; i < n; i++) { P[i] = make_pair(h[i], i); } sort(P.begin(), P.end()); for (int i = 0; i < n-1; i += 2) { ret.push_back(P[i].second); } ret.push_back(P[n-1].second); for (int i = n-2; i >= 1; i -= 2) { if (i%2 == 0) i--; ret.push_back(P[i].second); } return ret; } };