TopCoder SRM334 Div2 250Pts

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

3人の女の子がスーパーで買い物をしている。スーパーは1回のお買いもので$50以上の買い物をすると$10引くというセールを行っている。女の子たちは買うものをまとめれば、個別に買うよりも安く買えるということに気付いた。例えば、$46、$62、$9の品物を買うとすれば、$62、$46と$9の組合せによって、$20値引くことができる。goods[]という女の子たちがそれぞれ買った品物の合計額が入った整数型の配列が与えられる(3人なので要素数は3)。このとき、すべての品物を買うのに必要な最低費用を返せ。女の子たちは喜んで先述のように買い物をまとめようとするし、またどの子も買うものを分割するようなことはしないものとする。

私の解答はこちら。

import java.util.Arrays;

public class SupermarketDiscount {

 public int minAmount(int[] goods) {
  int nCosts = 0;
  int idx;
  Arrays.sort(goods);
  // $50以上のものはそれ単体で値引く
  for( idx=goods.length-1 ; idx>=0 ; idx-- ){
   if( goods[idx] >= 50 ){
    nCosts += goods[idx]-10;
   }else{
    break;
   }
  }
  int nTotal = 0;
  // 合わせて50を超えるようなことがあれば値引く
  for( int i=idx ; i>=0 ; i-- ){
   nTotal += goods[i];
   if( nTotal >= 50 ){
    nCosts += nTotal - 10;
    nTotal = 0;
   }
  }
  nCosts += nTotal;
  return nCosts;
 }

}

得点は228.21/250、中央値は約203点。結局面倒な実装はしなくても、先頭から順番に数えて$50を超えた時点で値引くということにすればOKということのようだった。気付けばなんてことのない実装になる。