Topcoder SRM 486 div2 1000 "CrazyLine"
問題:http://www.topcoder.com/stat?c=problem_statement&pm=10926 (要ログイン)
プラクティス.
身長のリストが与えられて,それを順番に並べたときの連続した身長差の合計の最大値を求める.
最大最小から順番に,交互に外側に並べていくと上手くいくようだ.
最後(真ん中)は両端のうち差が大きい方に追加する.
import java.util.Arrays; import java.util.LinkedList; public class CrazyLine { public int maxCrazyness(int[] heights) { int n = heights.length; Arrays.sort(heights); LinkedList<Integer> list = new LinkedList<Integer>(); int s = 0, e = n - 1; for (; s < e; ++s, --e) { list.addFirst(heights[e % 2 < 1 ? s : e]); list.addLast(heights[e % 2 < 1 ? e : s]); } if(s == e && list.size()>0){ int h = heights[s]; if(Math.abs(h - list.getFirst())<Math.abs(h -list.getLast())){ list.addLast(h); }else{ list.addFirst(h); } } int result = 0; for(int i = 0; i < n- 1; ++i){ result += Math.abs(list.get(i) - list.get(i+1)); } return result; } }