2012年2月14日火曜日

TopCoder SRM330 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

異なった数値からなる数列のsortnessというのは、各要素のsortnessの平均である。各要素のsortnessというのは、ある要素の前にそれより前に現れた大きな数と、それよりあとに現れた小さな数の出現回数である。sortnessが小さくなるにつれ、ソート済みの数列に近くなる。ソートされた数列ではsortnessは0になる。例えば{3,2,1,4}では、sortnessは(2+1+2+0)/4=1.25となる。各要素が異なる数からなる整数型の数列a[]が与えられたとき、aのsortnessを計算して返せ。

私の解答はこちら。

public class Sortness {

 public double getSortness(int[] a) {
  int nSortness = 0;
  for( int i=0 ; i<a.length ; i++ ){
   for( int j=0 ; j<a.length ; j++ ){
    if( i == j ){
     continue;
    }else if( i < j ){
     if( a[j] < a[i] ) nSortness++;
    }else{
     if( a[j] > a[i] ) nSortness++;
    }
   }
  }
  return (double)nSortness/a.length;
 }

}

得点は242.19/250、中央値は約234点。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計