TopCoder SRM468 Div2 250Pts

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

王は長いこと外におり、妃の元へできるだけ早く戻りたいと思っている。王は街0におり、妃は街Nにいる。0からN-1の間の値をとる各iにおいて、街iと街i+1を結ぶ道と空路が存在する。i番目の要素がiからi+1へ向かうのに陸路でかかる時間を表すroadTime[]と、空路でかかる時間flightTime[]が与えられる。しかし、空路を選ぶことは王国における技術的な制限により王の命に危険がある。したがって、妃は王に最大でK回のフライトにするように頼んでいる。王が妃のもとにたどり着くまでにかかる最小の時刻を計算して返せ。

私の解答はこちら。

import java.util.Arrays;

public class RoadOrFlightEasy {

 public int minTime(int N, int[] roadTime, int[] flightTime, int K) {
  int[] diff = new int[N];
  int time = 0;
  for( int i=0 ; i<N ; i++ ){
   diff[i] = roadTime[i] - flightTime[i];
  }
  for( int i=0 ; i<N ; i++ ){
   time += roadTime[i];
  }
  Arrays.sort(diff);
  if( diff[N-1] <= 0 ) return time;
  int k = 0;
  for( int i=N-1 ; i>=0 ; i-- ){
   if( k >= K || diff[i] <= 0 ) break;
   time -= diff[i];
   k++;
  }
  
  return time;
 }

}

得点は201.00/250、2回目のsubmitでシステムテストクリア。最後に「|| diff[i] <= 0」を付け忘れての失敗。方針としては、iからi+1へ陸路と空路で向かった時にかかる時間の差をとり、空路の方が速いものから、最大K個とるというものである(実際の計算では陸路で全部向かったと仮定して、差分だけ引き算するようにしている)。ただし、速い方からK個とるうちに、陸路の方が速く到着するようであれば、それ以上は空路を選択せずに終了とする。