TopCoder SRM242 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。それでは、問題について説明する。

ゲームで二つのチームにメンバーを分けるということをしたい。分けるためにまずはキャプテンを決める。そして交互にチームを作るためにプレーヤーを選択する。それぞれのターンでは一人ずつメンバーを選ぶ。キャプテンは強いメンバーが欲しいので、残っている中でベストなプレーヤーを選ぶ。プレーヤの強さはstrengths[]という配列で与えられており、値が大きいほど良いプレーヤーである。全員選び終えたところで、チームの強さというのはプレーヤーの強さの総和で計算される。二つのチームの強さの絶対値を返せ。

人数が奇数の時は先に選ぶキャプテンがとることになるため、2チームの人数は同じとは限らないことに注意。

私の解答はこちら。

import java.util.*;

public class TeamSplit {
 public int difference(int[] strengths) {
  int diff = 0;
  Arrays.sort(strengths);
  for( int i=0 ; i<strengths.length ; i++ ){
   if( i % 2 == 0 ){
    diff += strengths[strengths.length-i-1];
   }else{
    diff -= strengths[strengths.length-i-1];
   }
  }
  return diff;
 }
}

得点は236.44/250。ソートを楽にする方法がArrays.sortだった。最初から逆順から並べるにはコンパレータ使わないとダメかな?